{"id":"arxiv/2610.41371","url":"https://arxiv.org/abs/2610.41371","tags":["math.CO"],"score":0,"title":"$K_r$-Packings in Graphs with $t_{r-1}(n)+k$ Edges","domain":"math.CO","source":"arxiv","authors":["Hanzhi Bai","Fuhong Ma","Jin Yan"],"reviews":0,"subject":"math.CO","summary":"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{φ_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 $φ_r(n,k)$ has a long history and dates back to Erdős for the case $r=3$. \\rev{Győri} proved that $φ_r(n,k)=(1-o(1))k$ whenever $k=o(n^2)$. We characterize the range…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}