Erdős–Simonovits rational exponents conjecture — every rational in [1,2] is a Turán exponent

Statement

Erdős–Simonovits rational exponents conjecture (posed in Erdős, "On the combinatorial problems which I would most like to see solved," *Combinatorica* 1 (1981); see also erdosproblems.com/571 and erdosproblems.com/713 for the two closely related numbered forms). Call $r \in \mathbb{R}$ a Turán exponent if there is a graph (or family of graphs) $H$ with $$\mathrm{ex}(n,H) = \Theta(n^r),$$ where $\mathrm{ex}(n,H)$ is the largest number of edges in an $n$-vertex $H$-free graph. The conjecture:

> For every rational number $r \in [1,2]$, there is a single bipartite graph $H$ with $\mathrm{ex}(n,H) = \Theta(n^r)$.

Two weaker/adjacent forms recur in the literature and matter for how the conjecture is actually attacked: - Existence form (erdos/713): does *every* bipartite graph $G$ have *some* well-defined exponent $\alpha \in [1,2)$ with $\mathrm{ex}(n,G) \sim cn^\alpha$ — and must $\alpha$ be rational? - Family-relaxed form: same statement but $H$ is allowed to be a *finite family* $\mathcal{H}$ (forbid several graphs simultaneously) instead of one graph. This relaxed form is fully solved (Bukh–Conlon 2018, below); the single-graph form is the part that remains open.

Range restriction: $r=0$ (empty graph, trivial) and $r=2$ ($K_3$ or any graph with an odd cycle, by Erdős–Stone–Simonovits, since $\pi(H)>0$) are trivially realized; the entire content of the conjecture is the degenerate range $r \in (1,2)$, where $H$ must be bipartite (any non-bipartite $H$ forces $\mathrm{ex}(n,H)=\Theta(n^2)$ by Erdős–Stone–Simonovits, so exponents strictly between 1 and 2 can only come from bipartite — hence 2-chromatic, hence "degenerate" — forbidden graphs; see Turán number ex(n,H): extremal edge-count for forbidden subgraphs).

Facts

- Only known realisable exponents (as of the papers surveyed here) are of restricted closed forms, not a dense/complete set of $\mathbb{Q}\cap(1,2)$: - $1 + 1/k$ and $2 - 1/k$ for integers $k \ge 2$ — classical (Kővári–Sós–Turán / Bondy–Simonovits even-cycle upper bounds, matched by finite-geometry / algebraic lower-bound constructions). - $2 - 2/(2k+1)$ for $k \ge 2$, and $7/5$ via an asymmetric $\theta$-graph bound — He/Ma/Yang / Jiang–Ma line (arxiv.org/abs/1806.02838). - $2 - a/b$ for all integers $a,b \ge 1$ with $b > a$ and $b \equiv \pm 1 \pmod a$ — Kang, Kim, Liu, "On the rational Turán exponents conjecture," *JCTB* 148 (2021), arXiv:1811.06916. This subsumes the $2-1/k$, $2-2/k$ cases and produces infinitely many new closed-form exponents near 2. - $2 - a/b$ for all $a,b$ with $b \ge \max(a,(a-1)^2)$ — Conlon & Janzer, "Rational exponents near two," *Adv. Comb.* 2022:9, arXiv:2203.03375 (see Erdős–Simonovits rational exponents conjecture — the single-graph case near exponent 2 (Conlon–Janzer 2022) on this same wiki for the full proof-technique writeup). Strongest known single-graph result, still only covering rationals close to 2, not the whole interval. - $1 + p/q$ for all positive integers $p,q$ with $q > p^2$ — Jiang & Qiu, "Many Turán exponents via subdivisions," arXiv:1908.02385, covering rationals close to 1 by a dual (subdivision) construction. - The single-graph conjecture is wide open for exponents in the "middle" of $(1,2)$ (roughly $4/3$ to $5/3$) not covered by either the near-1 or near-2 families — no known technique currently reaches there. - The finite-family relaxation is fully solved: Bukh & Conlon, "Rational exponents in extremal graph theory," *J. Eur. Math. Soc.* 20.7 (2018) 1747–1757, arXiv:1506.06406 — for every rational $r \in [1,2]$ there is a finite family $\mathcal{H}_r$ with $\mathrm{ex}(n,\mathcal{H}_r) = \Theta(n^r)$. This is "arguably the main result towards" the single-graph conjecture (Conlon–Janzer's own framing) and supplies the reusable lower-bound machine (random algebraic method, below) that every subsequent single-graph paper reuses unchanged; only the matching upper bound for a genuine single $H$ is what each follow-up paper has to newly supply. - Kővári–Sós–Turán baseline: $\mathrm{ex}(n,K_{s,t}) = O(n^{2-1/s})$ (en.wikipedia.org/wiki/Zarankiewicz_problem), matched for $t$ large by finite-geometry constructions — this is the $s=t=k$ special case realizing $r=2-1/k$, and is the historical starting point of the whole rational-exponents program; see Turán number ex(n,H): extremal edge-count for forbidden subgraphs. - Sibling/companion conjecture — erdos/146 ($r$-degenerate bipartite $H \Rightarrow \mathrm{ex}(n,H)=O(n^{2-1/r})$): a formally distinct conjecture (about the *upper bound exponent forced by degeneracy*, universally quantified over all $r$-degenerate $H$) from the rational-exponents conjecture (about *which specific exponents are achievable*), but the two share essentially the same technique toolkit (random-algebraic lower bounds + dependent-random-choice/supersaturation upper bounds) and the same 1981/1984 Erdős–Simonovits paper of origin. See r-degeneracy — bounded induced-subgraph minimum degree (Lick–White; coloring number, Erdős–Hajnal) and Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$. - Induced/generalized variants under active 2025–2026 study: "Rational Exponents for Generalized Turán Numbers" (arXiv:2510.19621) and "Induced rational exponents near two" / "Induced rational exponents and bipartite subgraphs in $K_{s,s}$-free graphs" (arXiv:2604.05288, arXiv:2506.09020) extend the same question to generalized/induced Turán numbers — confirming this is a live, actively-generalizing research program as of the current date.

Technique

When it applies: whenever a problem asks "does there exist a graph (or forbidden family) whose extremal edge-count grows like exactly $n^r$ for a prescribed rational $r$ strictly between 1 and 2" — i.e. any degenerate/bipartite Turán-exponent *realizability* question, as opposed to bounding the exponent for a *given* $H$. The technique is a two-sided construction problem: you need a matching lower bound (an explicit $H$-free graph with $\Omega(n^r)$ edges) and upper bound (a proof that every $H$-free graph has $O(n^r)$ edges) for the *same* target exponent $r$, and the entire research program is organized around finding one flexible family of graphs $H$ where both sides can be pushed to match.

The engine — Bukh–Conlon's balanced-rooted-graph / blow-up framework (the key idea both sides of every paper in this cluster build on): 1. A rooted graph $(F,R)$ has *density* $\rho(F) = \rho_F(V(F)\setminus R)$ where $\rho_F(S) = e(S)/|S|$ (edges per non-root vertex). $(F,R)$ is balanced if $\rho_F(S) \ge \rho(F)$ for every $S \subseteq V(F)\setminus R$ — i.e. no sub-piece is denser (per non-root vertex) than the whole. 2. The $t$-blow-up $F^t$ glues $t$ vertex-disjoint copies of $F$ together at the root vertices $R$ (so the roots are shared, everything else is duplicated $t$-fold). 3. Lower bound (random algebraic method, reusable "off the shelf"): for balanced $F$ and $t$ large, $\mathrm{ex}(n,F^t) = \Omega(n^{2-1/\rho(F)})$, proved by taking the vertex set to be $\mathbb{F}_q^d$ (or a similar finite-field/algebraic-variety ground set) and joining two points when a random low-degree polynomial vanishes on them — a "random algebraic construction" in the tradition of norm graphs (Kollár–Rónyai–Szabó / Alon–Rónyai–Szabó). The randomness plus a Lang–Weil-type bound on the number of points on a variety controls both the edge count (giving $\Omega(n^{2-1/\rho})$ edges) and the absence of copies of $F^t$ (a copy would force too many simultaneous polynomial vanishings, which is generically avoided). This half of the machine has been fully general and solved since Bukh–Conlon 2018; see Random algebraic construction (Bukh; Bukh–Conlon) — random low-degree polynomials over $\\mathbb F_q$ for Turán lower bounds on this same wiki. 4. Upper bound (open in general — "Conjecture 1.4" of Bukh–Conlon): is it true that for every balanced rooted tree $F$, $\mathrm{ex}(n,F^t) = O(n^{2-1/\rho(F)})$ too, matching the lower bound? If this held for all balanced rooted trees $F$, it would immediately imply the *full* rational-exponents conjecture (because $\rho(F)$ ranges densely over enough rationals as $F$ varies). This is exactly why the single-graph conjecture has progressed as a sequence of papers, each proving the matching upper bound for a wider family of specific rooted trees $F$ — not as one global argument: - Jiang, Ma & Yepremyan (2022); Kang–Kim–Liu (arXiv:1811.06916, $b \equiv \pm1 \bmod a$); Conlon–Janzer–Lee (2021); Janzer (2020); Jiang–Ma–Yepremyan's successors Jiang–Jiang–Ma ("Negligible obstructions and Turán exponents," 2022, tree family $F_{r,s}$ under $r \ge s^3-1$); Conlon–Janzer (arXiv:2203.03375, same $F_{r,s}$ under the much weaker $r \ge s+2$, via a simpler codegree-counting argument — see Erdős–Simonovits rational exponents conjecture — the single-graph case near exponent 2 (Conlon–Janzer 2022)). 5. The upper-bound technique itself, when it succeeds, is a codegree/dependent-random-choice argument, not new algebra: reduce to an almost-regular bipartite host graph (Erdős–Simonovits / Conlon–Lee reduction), classify high-degree "stars" as heavy (would themselves force a copy of $H$ if too frequent) vs. light, and show that avoiding $H$ forces an anomalously dense bipartite pattern which — via a dependent-random-choice-style double-counting closing argument — itself must contain $H$, a contradiction. See Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts. 6. Bootstrap device (Kang–Kim–Liu): once one balanced rooted graph $F$ with $a = $ (a parameter derived from $\rho(F)$) is shown to realize exponent $2 - a/(ap_0+q)$ via its $t$-blow-up for one specific $p_0$, the *same* $F$ (with varying blow-up parameter) automatically realizes $2 - a/(ap+q)$ for every $p \ge p_0$ — so solving Conjecture 1.4 for a single balanced tree $F$ yields an infinite closed-form family of denominators for free, not just one exponent. This is the mechanism by which each new paper's headline result ("$2-a/b$ realisable for [some congruence/inequality condition on $a,b$]") gets its clean closed form.

Why it works (the mechanism): the conjecture is fundamentally a *matching-exponents* problem, and blow-ups of a fixed rooted graph give a one-parameter family ($t$) whose lower-bound exponent $2-1/\rho(F)$ is *fixed by $F$ alone* (independent of $t$) — so once you find, for a target rational $r$, some balanced rooted tree $F$ with $\rho(F) = 1/(2-r)$, the *only* remaining work is proving the matching upper bound for that specific $F$'s blow-ups, which is a finite, self-contained combinatorial problem (not requiring new algebraic constructions, since the hard, general-purpose lower-bound half is already solved). This decomposition — "reduce realizability of a rational number to finding + analyzing a suitable balanced rooted tree" — is the reusable derivation hook: any advance either (a) exhibits a new balanced rooted tree $F$ hitting a previously-unreached $\rho(F)$, or (b) proves Conjecture 1.4 for a wider class of already-known trees, and either move directly yields new closed-form realisable exponents via the bootstrap.

Recipe for using this to attack an adjacent problem: 1. Identify the target rational $r \in (1,2)$; compute the required rooted-graph density $\rho = 1/(2-r)$. 2. Search for (or construct) a balanced rooted tree $F$ with $\rho(F) = \rho$ — the tree family $F_{r,s}$ (center $y$, $r$ middle vertices each joined to $y$ and to $s$ leaves as roots) used by Jiang–Jiang–Ma and Conlon–Janzer is the current best-understood flexible parametrized family, with $\rho(F_{r,s}) = (rs+r)/(r+1)$. 3. The lower bound $\Omega(n^{2-1/\rho})$ is then free via Bukh–Conlon's random algebraic method. 4. The remaining work is the upper bound: reduce to an almost-regular bipartite host, run the heavy/light-star codegree-counting + dependent-random-choice closing argument (step 5 above) — this is where all the genuine technical difficulty of the whole research program lives. 5. Feed the result through the Kang–Kim–Liu bootstrap to convert one solved case into an infinite closed-form family.

Related

- Erdős #713 — does every bipartite graph have a Turán exponent? — the existence/rationality question ("does every bipartite graph have *some* Turán exponent, and is it rational?"); the weaker existential cousin of this conjecture, same 1970s–80s Erdős–Simonovits origin, same toolkit. - Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — the $r$-degenerate-bipartite-forces-$O(n^{2-1/r})$ conjecture; a formally distinct but methodologically identical sibling conjecture from the same Erdős–Simonovits 1981/1984 program. - Erdős–Simonovits rational exponents conjecture — the single-graph case near exponent 2 (Conlon–Janzer 2022) — the fully-worked single-graph proof (Conlon–Janzer 2022) of the $r$ near 2 sub-case, with the complete technique writeup (balanced rooted trees, heavy/light stars, rich-copy collision argument) this page summarizes. - Turán number ex(n,H): extremal edge-count for forbidden subgraphs — $\mathrm{ex}(n,H)$, the extremal quantity this whole conjecture is about; also covers Kővári–Sós–Turán and Erdős–Stone–Simonovits background needed to see why $r\in(1,2)$ is the only nontrivial range. - r-degeneracy — bounded induced-subgraph minimum degree (Lick–White; coloring number, Erdős–Hajnal) — $r$-degeneracy, the structural notion controlling which bipartite $H$ can even plausibly realize a sub-quadratic exponent; shared hypothesis-space with Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$. - Dependent random choice — pick a small random test-tuple, take its common neighborhood; the resulting set is large and almost every small subset of it still has a large common neighborhood, giving a workhorse for embedding sparse/bipartite graphs into dense hosts — the codegree-counting workhorse that supplies every known matching upper bound in this cluster (step 5 of the Technique section above). - Random algebraic construction (Bukh; Bukh–Conlon) — random low-degree polynomials over $\\mathbb F_q$ for Turán lower bounds — Bukh's random low-degree-polynomial method; supplies the fully-general, already-solved lower-bound half of every result in this cluster. - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — combined with codegree/dependent-random-choice arguments in the tree-blow-up upper-bound proofs (Grzesik–Janzer–Nagy line, shared machinery with Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$'s partial results).