A conjecture of Brown, Erdős, and Sós [BES73]. The answer is yes, proved by Ruzsa and Szemerédi [RuSz78] (this is known as the Ruzsa-Szemerédi problem).

In [Er75b] and [Er81] Erdős asks whether the same is true for the collection of all $3$-uniform hypergraph on $k$ vertices with $k-3$ $3$-edges. In [Er75b] he even asks whether, for such $\mathcal{F}$,\[\mathrm{ex}_3(n,\mathcal{F})\asymp n r_{k-3}(n),\]where $r_{k-3}(n)$ is the maximal size of a subset of $\{1,\ldots,n\}$ that does not contain a non-trivial arithmetic progression of length $k-3$. He states that Ruzsa has proved the lower bound for $k=6,7,8$.

View the LaTeX source

This page was last edited 06 October 2025.