Conjectured by Erdős and Simonovits [ErSi84]. A probabilistic argument shows that there exists some $\epsilon=\epsilon(H)>0$ such that\[\mathrm{ex}(n;H) \gg n^{2-\frac{2}{r}+\epsilon}.\]This conjecture was disproved by Janzer [Ja23] for even $r\geq 4$. The case $r=3$ was disproved by Janzer [Ja23b], who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that\[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]In [Ja23] Janzer conjectures that the above lower bound is sharp, in that for any $r\geq 3$ and $\epsilon>0$ there exists an $r$-regular graph $H$ such that\[\mathrm{ex}(n;H) \ll n^{2-\frac{2}{r}+\epsilon}.\]Janzer's result proves this for even $r\geq 4$.

See also [113], [146], and [714].

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

View the LaTeX source

This page was last edited 18 January 2026.