A conjecture of Brown, Erdős, and Sós [BES73], who proved that $d_r(e)\geq (r-2)e+3$ (see also [1076]).

Ruzsa and Szemerédi [RuSz78] proved $d_3(3)=6$ (see [716]).

Erdős, Frankl, and Rödl [EFR86] proved\[d_r(3)= (r-2)3+3\]for all $r\geq 3$. Sárközy and Selkow [SaSe05] proved\[d_r(e) \leq (r-2)e+2+\lfloor \log_2 e\rfloor\]for all $r,e\geq 3$. Solymosi and Solymosi [SoSo17] proved that $d_3(10)\leq 14$. Conlon, Gishboliner, Levanzov, and Shapira [CGLS23] proved\[d_3(e)\leq e+O\left(\frac{\log e}{\log\log e}\right)\]for all $e\geq 3$.

In [Er75b] Erdős even asks whether, if $\mathcal{F}$ is the family of $3$-uniform hypergraphs on $k$ vertices with $k-3$ edges,\[\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$.

See [1157] for the general case.

View the LaTeX source

This page was last edited 26 January 2026.