Rational exponents for bipartite Turán numbers

For a bipartite graph $G$, the largest number of edges in an $n$-vertex graph with no copy of $G$ is at most $n^{2-\varepsilon}$ for some $\varepsilon>0$, but for most $G$ its true order of growth is unknown. Erdős and Simonovits asked whether the growth is always a clean power law $cn^{\alpha}$, and whether the exponent $\alpha$ must be rational. Erdős offered $500 for an answer.

Problem

For a graph $G$ let $\mathrm{ex}(n;G)$ be the maximum number of edges in a graph on $n$ vertices that contains no copy of $G$. Is it true that for every bipartite graph $G$ there are constants $\alpha\in[1,2)$ and $c>0$ such that

$$\mathrm{ex}(n;G)\sim c\,n^{\alpha}\,?$$

Must $\alpha$ be rational? Erdős sometimes asked the weaker question with $\mathrm{ex}(n;G)\asymp n^{\alpha}$ in place of an asymptotic formula.

Background

For non-bipartite $G$ the Erdős–Stone–Simonovits theorem determines $\mathrm{ex}(n;G)$ up to $o(n^2)$, so the degenerate, bipartite case is where the real difficulty lies. Erdős first conjectured (1967) that the exponent is always of the form $1+\frac1k$ or $2-\frac1k$, but Erdős and Simonovits disproved this in 1970. The question of which exponents occur is often called the rational exponents conjecture; Füredi and Simonovits (2013) survey its history.

What is known

• Every rational occurs. Bukh and Conlon (2018) proved that for every rational $r\in[1,2]$ there is a finite family $\mathcal H_r$ of graphs with $\mathrm{ex}(n,\mathcal H_r)=\Theta(n^{r})$. The single-graph version, that every rational $\alpha\in[1,2)$ is the exponent of one bipartite graph (problem 571, the rational exponents conjecture), was proved in 2026 with a Lean formalisation; Conlon, Janzer, Jiang, Kim, Lee, Liu, Longbrake and Yepremyan have written an exposition. So every rational exponent occurs; the question here is the converse.
• Existence of an exponent. Even the weaker statement $\mathrm{ex}(n;G)\asymp n^{\alpha}$ for some $\alpha$ is open for general bipartite $G$. The exponent is known exactly only for special families of bipartite graphs, which the survey of Füredi and Simonovits lists.
• Hypergraphs behave differently. Frankl and Füredi (1987) found a 5-uniform hypergraph $H$ with $\mathrm{ex}(n,H)=o(n^4)$ but $\mathrm{ex}(n,H)\ne O(n^{4-\varepsilon})$ for every $\varepsilon>0$, so no exponent exists. Füredi and Gerbner extended this to every uniformity $k\ge5$ and conjecture it for $k=3,4$; the question here is whether it can happen for graphs.

What would count as progress

• A bipartite graph $G$ for which $\mathrm{ex}(n;G)=\Theta(n^{\alpha})$ with $\alpha$ irrational, or for which no exponent exists; this would answer the question negatively.
• A proof that $\mathrm{ex}(n;G)=\Theta(n^{\alpha})$ for some rational $\alpha$ for a substantial new class of bipartite graphs, or asymptotic formulas $\mathrm{ex}(n;G)\sim cn^{\alpha}$ for new graphs $G$.
• A formal proof against the Lean statement in formal-conjectures.

References

1. B. Bukh and D. Conlon, Rational exponents in extremal graph theory, J. Eur. Math. Soc. 20 (2018), 1747–1757. doi:10.4171/JEMS/798
2. Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, in Erdős Centennial, Bolyai Soc. Math. Stud. 25 (2013), 169–264. doi:10.1007/978-3-642-39286-3_7
3. D. Conlon, O. Janzer, T. Jiang, J. Kim, J. Lee, H. Liu, S. Longbrake and L. Yepremyan, A proof of the rational exponents conjecture (2026). arXiv:2610.18713
4. Z. Füredi and D. Gerbner, Hypergraphs without exponents (2019). arXiv:1906.06657

Source

Imported from Erdős Problems 713, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.