Rational Turán exponents: is every rational $\alpha\in[1,2)$ the exponent of $\mathrm{ex}(n;G)$ for some bipartite $G$? (Erdős #571)
Statement
For a graph $G$, let $\mathrm{ex}(n;G)$ be the maximum number of edges in an $n$-vertex graph with no copy of $G$. Write $f(n)\asymp n^{\alpha}$ to mean $c_1 n^{\alpha}\leq f(n)\leq c_2 n^{\alpha}$ for constants $0<c_1\leq c_2$ and all large $n$. Conjecture (Erdős–Simonovits): for every rational number $\alpha\in[1,2)$ there exists a finite bipartite graph $G$ with $$\mathrm{ex}(n;G)\asymp n^{\alpha}.$$ A rational $\alpha\in[1,2)$ that is realized this way is called a Turán exponent; the conjecture asks that every rational in $[1,2)$ be a Turán exponent.
Acceptance. FULLY RESOLVES: a complete proof that every rational $\alpha\in[1,2)$ is a Turán exponent — i.e. for each such $\alpha$ a bipartite graph $G_\alpha$ (or an existence argument) with matching proven bounds $\mathrm{ex}(n;G_\alpha)\asymp n^{\alpha}$ — OR a disproof: a specific rational in $[1,2)$ shown, with proof, not to be a Turán exponent. Machine-checkable proof preferred, else a full written proof with all steps. ADVANCES: establish a NEW rational $\alpha\in[1,2)$, or a new infinite family of rationals, as Turán exponent(s) not contained in the families listed in the background — by exhibiting a bipartite $G$ with proofs of BOTH the matching upper bound $\mathrm{ex}(n;G)\ll n^{\alpha}$ and lower bound $\mathrm{ex}(n;G)\gg n^{\alpha}$; or extend the Bukh–Conlon finite-family realization to single graphs over a new range of rationals. Deliver the graph construction and the proofs of the matching upper and lower bounds (or the impossibility proof).
Background
A problem of Erdős and Simonovits; in [Er78] Erdős cautioned 'I am not entirely sure that a trivial counterexample can not be found.' Only exponents in $[1,2)$ can occur for bipartite $G$, and all known bipartite Turán numbers have rational exponents, which motivates the conjecture. Landmark partial result: Bukh and Conlon [BuCo18] proved the statement if one is allowed to forbid a finite FAMILY of graphs rather than a single graph — every rational in $[1,2)$ is the exponent of $\mathrm{ex}(n;\mathcal{F})$ for some finite family $\mathcal{F}$. For single graphs a growing list of Turán exponents is known: $\tfrac{3}{2}-\tfrac{1}{2s}$ for $s\geq 2$ (Conlon–Janzer–Lee [CJL21]); $\tfrac{4}{3}-\tfrac{1}{3s}$ and $\tfrac{5}{4}-\tfrac{1}{4s}$ for $s\geq 2$ (Jiang–Qiu [JiQi20]); $2-\tfrac{a}{b}$ in various ranges (Jiang–Jiang–Ma [JJM20]; Kang–Kim–Liu [KKL21], with $b\equiv\pm1\pmod a$; Conlon–Janzer [CoJa22], with $b\geq(a-1)^2$); $1+\tfrac{a}{b}$ with $b>a^2$ (Jiang–Qiu [JiQi23]); and $2-\tfrac{2}{2b+1}$ for $b\geq 2$, plus $7/5$ (Jiang–Ma–Yepremyan [JMY22]). The full conjecture — every rational in $[1,2)$ for a single graph — remains open. Related: Erdős #713 (erdosproblems.com/713); this is #45 in the Extremal Graph Theory problem collection. Listed as open on erdosproblems.com/571 (fetched 2026-07-13, status 'open'), tagged graph theory | turan number. Attacker's tool: explicit and random algebraic constructions of bipartite graphs with prescribed extremal growth (random polynomial/norm graphs, blow-ups, tensor powers) paired with matching upper bounds via counting — establishing a single new rational exponent is a concrete, checkable advance.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #571 (T. F. Bloom) | website |
| REF-02 | Extremal Graph Theory collection #45 — rational Turán exponents | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.