Problem 1020

Erdős Problem #1020 [status: falsifiable; formalized: no]. Let $f(n;r,k)$ be the maximal number of edges in an $r$-uniform hypergraph which contains no set of $k$ many independent edges. For all $r\geq 3$,$$f(n;r,k)=\max\left(\binom{rk-1}{r}, \binom{n}{r}-\binom{n-k+1}{r}\right).$$ Current best: The conjectured form of $f(n;r,k)$ is the best possible, as witnessed by two examples: all $r$-edges on a set of $rk-1$ many vertices, and all edges on a set of $n$ vertices which contain at least one element of a fixed set of $k-1$ vertices. Note that the second term in the maximum dominates when $n\geq (r+1)k$. For small $n$: {UL} {LI}The conjecture is trivially true if $n<kr$.{/LI} {LI}Kleitman [Kl68] when $n=kr$.{/LI} {LI}Frankl [Fr17] when$$kr \leq n\leq k\left(r+\frac{1}{2r^{2r+1}}\right).$${/LI} {LI}Kolupaev and Kupavskii [KoKu23] when $r\geq 5$, $k>101r^3$, and$$kr \leq n < k\left(r+\frac{1}{100r}\right).$${/LI} {/UL} For large $n$: {UL} {LI}Erd\H{o}s [Er65d] when $n>kc_r$ (where $c_r$ depends on $r$ in some unspecified fashion).{/LI} {LI} Frankl and F\"{u}redi [Fr87] when $n>100 k^2r$.{/LI} {LI} Bollob\'{a}s, Daykin, and Erd\H{o}s [BDE76] when $n\geq 2kr^3$.{/LI} {LI} Frankl, R\"{o}dl, and Ruci\'{n}ski [FRR12] when $r=3$ and $n\geq 4k$.{/LI} {LI} Huang, Loh, and Sudakov [HLS12] when $n\geq 3kr^2$.{/LI} {LI} Frankl, Luczak, and Mieczkowska [FLM12] when $n> 2k\frac{r^2}{\log r}$.{/LI} {LI} Luczak and Mieczkowska [LuMi14] when Prize: no. Tags: graph theory, hypergraphs.