Logo
All Random Solved Random Open
OPEN
Let $f(n;t)$ be minimal such that if a $t$-uniform hypergraph on $n$ vertices contains at least $f(n;t)$ edges then there must be four edges $A,B,C,D$ such that \[A\cup B= C\cup D\] and \[A\cap B=C\cap D=\emptyset.\] Estimate $f(n;t)$ - in particular, is it true that for $t\geq 3$ \[f(n;t)=(1+o(1))\binom{n}{t-1}?\]
For $n=2$ this is asking for the maximal number of edges on a graph which contains no $C_4$, and so $f(n;2)=(1+o(1))n^{3/2}$.

Füredi proved that $f(n;3) \ll n^2$ and $f(n;3) > \binom{n}{2}$ for infinitely many $n$. More generally, Füredi proved that \[f(n;t) \ll \binom{n}{t-1}.\]