Logo
All Random Solved Random Open
OPEN - $500
Is it true that, for every bipartite graph $G$, there exists some $\alpha\in [0,1)$ such that \[\lim_{n\to \infty}\frac{\mathrm{ex}(n;G)}{n^{1+\alpha}}\] exists and is in $(0,\infty)$?
A problem of Erdős and Simonovits. This is not true for hypergraphs, as shown by Ruzsa and Szemerédi [RuSz78], who proved that if $G$ is a $3$-uniform hypergraph on $6$ vertices containing $3$ $3$-edges then $\mathrm{ex}_3(n;G)=o(n^2)$ and yet for every $\epsilon >0$ \[\mathrm{ex}_3(n;G) >n^{2-\epsilon}\] for all large enough $n$.

See also [571].