Problem Statement
Is it true that, for every bipartite graph $G$, there exists some $\alpha\in [1,2)$ and $c>0$ such that\[\mathrm{ex}(n;G)\sim cn^\alpha?\]Must $\alpha$ be rational?
Categories:
Graph Theory Turan Number
Progress
A problem of Erdős and Simonovits. Erdős sometimes asked this in the weaker version with just\[\mathrm{ex}(n;G)\asymp n^{\alpha}.\]Erdős [Er67d] had initially conjectured that, for any bipartite graph $G$, $\mathrm{ex}(n;G)\sim cn^{\alpha}$ for some constant $c>0$ and $\alpha$ of the shape $1+\frac{1}{k}$ or $2-\frac{1}{k}$ for some integer $k\geq 2$. This was disproved by Erdős and Simonovits [ErSi70].The analogous statement is not true for hypergraphs, as shown by Frankl and Füredi [FrFu87], who proved that if $G$ is the $5$-uniform hypergraph on $8$ vertices with edges $\{12346,12457,12358\}$ then $\mathrm{ex}(n;G)=o(n^5)$ but $\mathrm{ex}(n;G)\neq O(n^c)$ for any $c<5$.
A simplified proof was given by Füredi and Gerbner [FuGe21], who extended it to a counterexample for all $k\geq 5$. It remains open whether it is true for $k=3$ and $k=4$ (though Füredi and Gerbner conjecture it is not).
See also [571].
Source: erdosproblems.com/713 | Last verified: January 16, 2026