Metraipolis › archive › dc_592cd3278546

$K_r$-Packings in Graphs with $t_{r-1}(n)+k$ Edges — arXiv:2610.41371

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41371
License (as archived)
CC0-1.0
Archived
2026-11-02T05:00:36.027Z
SHA-256 of the archived text
d65e0bf86aa9aedfd67541a10f9d12ef787a6fdc32f2d253faba962c278177e9
Stable URL of this page
https://metraipolis.com/documento/dc_592cd3278546

How to cite

$K_r$-Packings in Graphs with $t_{r-1}(n)+k$ Edges — arXiv:2610.41371 — arXiv (en), https://arxiv.org/abs/2610.41371 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_592cd3278546 (Metraipolis archive dc_592cd3278546, sha256 d65e0bf86aa9aedfd67541a10f9d12ef787a6fdc32f2d253faba962c278177e9)
BibTeX
@misc{dc592cd3278546,
  title = {$K_r$-Packings in Graphs with $t_r-1(n)+k$ Edges — arXiv:2610.41371},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41371},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_592cd3278546; sha256 d65e0bf86aa9aedfd67541a10f9d12ef787a6fdc32f2d253faba962c278177e9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41371. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Fix an integer $r\ge 3$. Let $K_r$ denote the complete graph on $r$ vertices and $t_{r-1}(n)$ the Turán number for $K_r$. For each integer $k$ satisfying $0\le k \le \binom{n}{2}-t_{r-1}(n)$, $\rev{\phi_r(n,k)}$ denotes the minimum, over all $n$-vertex graphs with $t_{r-1}(n)+k$ edges, of the maximum size of a $K_r$-packing \rev{(a family of edge-disjoint copies of $K_r$)} in the graph. The problem of characterizing the behavior of $\phi_r(n,k)$ has a long history and dates back to Erdős for the case $r=3$. \rev{Győri} proved that $\phi_r(n,k)=(1-o(1))k$ whenever $k=o(n^2)$. We characterize the range of $k$ for which $\phi_r(n,k)=(1-o(1))k$, showing that this equality holds if and only if $k=o(n^2)$. Moreover, we obtain an \rev{asymptotic} upper bound (which falls below $1$) for $\phi_r(n,k)/k$ whenever $k/n^2$ converges to a constant $\delta$ satisfying $0 < \delta \le \frac{1}{2(r-1)}$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.41371 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T04:47:57.680Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).