Erdős #643 · graph theory / hypergraphs

For $t=2$ this is asking for the maximal number of edges on a graph which contains no $C_4$, and so $f(n;2)=(1/2+o(1))n^{3/2}$.

Füredi [Fu84] proved that $f(n;3) \ll n^2$ and $f(n;3) > \binom{n}{2}$ for infinitely many $n$. Pikhurko and Verstraëte [PiVe09] have proved $f(n;3)\leq \frac{13}{9}\binom{n}{2}$ for all $n$.

More generally, Füredi [Fu84] proved that

and conjectured the lower bound is sharp for $t\geq 4$. Pikhurko and Verstraëte [PiVe09] have proved that

for all $t\geq 3$.

Füredi [Fu84] proved that $f(n;3)/\binom{n}{2}$ converges as $n\to \infty$, but the existence of the limit for $t\geq 4$ is unknown.

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.