Do bipartite Turán numbers have the form $c\,n^\alpha$ with rational $\alpha$? (Erdős #713)
Statement
For a bipartite graph $G$, let $\mathrm{ex}(n;G)$ be the maximum number of edges in an $n$-vertex graph with no copy of $G$ (this is always $o(n^2)$). Conjecture (Erdős–Simonovits): for every bipartite graph $G$ there exist a real number $\alpha\in[1,2)$ and a constant $c>0$ such that $$\mathrm{ex}(n;G)\sim c\,n^{\alpha}.$$ Moreover, must the exponent $\alpha$ always be rational? A weaker (also open) form asks only for $\mathrm{ex}(n;G)\asymp n^{\alpha}$, i.e. the exponent alone, without a limiting constant.
Acceptance. FULLY RESOLVES: a complete proof that every bipartite graph $G$ admits $\alpha\in[1,2)$ and $c>0$ with $\mathrm{ex}(n;G)\sim c\,n^{\alpha}$, together with a proof that $\alpha$ is always rational; OR a counterexample — a specific bipartite $G$ for which the limit $\mathrm{ex}(n;G)/n^{\alpha}$ fails to exist for every $\alpha$, or whose growth exponent is provably irrational — in each case with all steps given (machine-checkable proof preferred). ADVANCES: establish the sharp form $\mathrm{ex}(n;G)\sim c\,n^{\alpha}$ (existence of the limiting constant) for a new infinite class of bipartite graphs where only $\asymp n^{\alpha}$ was previously known; or prove or disprove the rationality of the exponent for a specific bipartite graph whose exponent is currently unknown — each with complete proof. Deliver the proof file, or the explicit counterexample graph together with its growth-rate proof.
Background
A problem of Erdős and Simonovits [ErSi70, ErSi84], with further mentions in [Er75, Er78, Er81, Er91]; Erdős offered \$500 for a solution. Erdős [Er67d] first conjectured that every bipartite $G$ has $\mathrm{ex}(n;G)\sim c\,n^{\alpha}$ with $\alpha$ of the special form $1+\tfrac1k$ or $2-\tfrac1k$ ($k\ge 2$ an integer); that restricted form was disproved by Erdős–Simonovits [ErSi70]. Whether the limit (the $\sim$, not just $\asymp$) exists and whether $\alpha$ is always rational both remain open. The hypergraph analogue is FALSE: Frankl–Füredi [FrFu87] exhibited a $5$-uniform $8$-vertex hypergraph $G$ (edges $\{12346,12457,12358\}$) with $\mathrm{ex}(n;G)=o(n^5)$ yet $\mathrm{ex}(n;G)\ne O(n^c)$ for any $c<5$; Füredi–Gerbner [FuGe21] gave a simplified proof and extended the counterexample to all $k\ge 5$, leaving $k=3,4$ open (they conjecture it also fails there). Related to Erdős #571 (erdosproblems.com/571). Listed as open on erdosproblems.com/713 (fetched 2026-07-13, status 'open', tagged 'graph theory | turan number'). Attacker's tool: proof-shaped — a bipartite $G$ whose Turán exponent is provably irrational, or for which the limiting constant fails to exist, would disprove the conjecture, while a proof would likely require new supersaturation/entropy machinery; Bukh–Conlon-style random-algebraic constructions (which realise a wide set of rational exponents) are the natural probing ground.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #713 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.