Erdős and Simonovits [ErSi70] proved that\[(\tfrac{1}{2}+o(1))n^{3/2}\leq \mathrm{ex}(n;Q_3) \ll n^{8/5}.\](In [ErSi70] they mention that Erdős had originally conjectured that $ \mathrm{ex}(n;Q_3)\gg n^{5/3}$.) Erdős and Simonovits also proved that, if $G$ is the graph $Q_3$ with a missing edge, then $\mathrm{ex}(n;G)\asymp n^{3/2}$.

In [Er74c], [Er81], and [Er93] Erdős asked whether it is $\mathrm{ex}(n;Q_3)\asymp n^{8/5}$.

A theorem of Sudakov and Tomon [SuTo22] implies\[\mathrm{ex}(n;Q_k)=o(n^{2-\frac{1}{k}}).\]Janzer and Sudakov [JaSu22] have improved this to\[\mathrm{ex}(n;Q_k)\ll_k n^{2-\frac{1}{k-1}+\frac{1}{(k-1)2^{k-1}}}.\]See also [1035].

This problem is #52 in Extremal Graph Theory in the graphs problem collection.

View the LaTeX source

This page was last edited 18 January 2026.