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

Abstract

Fix an integer $r\ge 3$. Let $K_r$ denote the complete graph on $r$ vertices and $t_{r-1}(n)$ the Tur\'an 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\H{o}s for the case $r=3$. \rev{Gy\H{o}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)}$.