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