Skip to content
Preprint

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

Oct 2026 · 0 citations · 5 references
Mathematics

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)}$.

View source

Similar papers

Preprint Sep 2026

Tur\'an problems with bounded matching number in $k$-uniform hypergraphs

For a family $\mathcal{F}$ of $k$-graphs, $ex_k(n,\mathcal{F})$ denotes the maximum number of edges in an $n$-vertex $\mathcal{F}$-free $k$-graph. Let $M_{s+1}^k$ denote a matching of size $s+1$ in $k$-uniform hypergraphs. Recently, Alon and Frankl (JCTB, 2024) determined $ex_2(n,\{M_{s+1}^2,K_{\ell+1}\})$ for all $n\g...

Jia-Lin Liu, Ming-Yang Guo, Xiu-Mei Wang · 0 citations
Preprint Nov 2026

Rational Tur\'an exponents of a single $k$-uniform hypergraph

For a fixed $k$-uniform hypergraph $F$, let $\mathrm{ex}_k(n,F)$ denote the maximum number of edges in an $F$-free $k$-uniform hypergraph on $n$ vertices. We prove that for every integer $k\ge2$ and every rational $r\in[0,1]$ there exists a $k$-uniform hypergraph $F_{k,r}$ such that \begin{equation*} \mathrm{ex}_k(n,F_...

Chang Liu, Jue Dai · 0 citations
Preprint Oct 2026

Tur\'an densities of hypergraph augmentations

For a $t$-graph $F$ and an integer $r\ge t$, the \emph{$r$-augmentation} $F(r)$ is the $r$-graph obtained by adding the same set of $r-t$ new vertices to every edge of $F$. We investigate the behaviour of the \emph{Tur\'an density $\pi(F(r))$}, which is the asymptotically maximum edge density of a large $F(r)$-free $r$...

Oleg Pikhurko, Jia-Bao Yang, Xiu-Tao Zhu · 0 citations
Preprint Sep 2026

The Erd\H{o}s--Hajnal hypergraph Ramsey problem for $r_4(6,n)$

The Ramsey number $r_k(s,n)$ is the smallest integer $N$ such that every $N$-vertex $k$-graph contains either a copy of $K_s^{(k)}$ or an independent set of size $n$. Erd\H{o}s and Hajnal conjectured that for every fixed $s>k\ge 4$, one has $r_k(s,n)\ge \operatorname{twr}_{k-1}(\Omega(n))$. This conjecture was independ...

Long-Ma Du, Xin-Yu Hu, Rui-Long Liu et al. · 0 citations
Preprint Sep 2026

Counting hypergraphs without linear cycles of fixed length

Let $C_{k}^{(r)}$ be the $r$-uniform linear cycle on $k$ hyperedges. An $r$-graph is $C_{k}^{(r)}$-free if it contains no copy of $C_{k}^{(r)}$. Let $\operatorname{ex}_{r}(n,C_{k}^{(r)})$ denote the maximum number of hyperedges in an $n$-vertex $C_{k}^{(r)}$-free $r$-graph. Balogh, Narayanan and Skokan asked whether, f...

József Balogh, Ramon I. Garcia, Abhishek Methuku · 0 citations
Preprint Oct 2026

Induced-Count Discrepancy in Uniform Hypergraphs

Let $u_k^{(r)}(H,p)$ be the maximum, over all $k$-vertex $r$-uniform hypergraphs $F$, of the absolute difference between the number of induced copies of $F$ in $H$ and its expectation in the binomial random $r$-graph with the same number of vertices as $H$ and edge probability $p$. Let $u_k^{(r)}(n,p)$ be the minimum o...

Cheng-Long Yu · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.