Problem Statement
Let $\mathcal{F}$ be the family of all $3$-uniform hypergraphs with $6$ vertices and $3$ $3$-edges. Is it true that\[\mathrm{ex}_3(n,\mathcal{F})=o(n^2)?\]
Categories:
Graph Theory Hypergraphs
Progress
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$.
Source: erdosproblems.com/716 | Last verified: January 16, 2026