Erdős–Simonovits rational exponents conjecture — the single-graph case near exponent 2 (Conlon–Janzer 2022)

Statement

The Erdős–Simonovits rational exponents conjecture (P. Erdős, "On the combinatorial problems which I would most like to see solved," *Combinatorica* 1 (1981)): for every rational number $r\in[1,2]$, there exists a single graph $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. This is the *single-graph* (strong) form; it remains open in general. The problem addressed in this page is the sub-case near the top endpoint $r=2$:

Theorem (Conlon–Janzer 2022). All rationals of the form $r = 2 - a/b$ with $b \ge \max(a,(a-1)^2)$ are realisable by a single graph. This proves, in a strong quantitative form, a conjecture of Jiang, Jiang and Ma (their Conjecture 11) that all rationals sufficiently close to 2 are realisable.

Facts

- Origin of the field's real breakthrough: Bukh & Conlon, "Rational exponents in extremal graph theory," *J. Eur. Math. Soc.* 20 (2018), arXiv:1506.06406, proved the conjecture for finite families $\mathcal H$ of graphs (i.e. $\mathrm{ex}(n,\mathcal H)=\Theta(n^r)$ for every rational $r\in[1,2]$), leaving the single-graph form open. This is "arguably the main result towards" the conjecture (Conlon–Janzer, §1). - Bukh–Conlon's structural framework, which all later single-graph papers (including Conlon–Janzer) build on: a *rooted graph* $(F,R)$ has density $\rho(F)=\rho_F(V(F)\setminus R)$ where $\rho_F(S)=e_S/|S|$; $(F,R)$ is balanced if $\rho_F(S)\ge\rho(F)$ for every $S\subseteq V(F)\setminus R$. The $t$-blowup $F^t$ glues $t$ vertex-disjoint copies of $F$ at the roots. Bukh–Conlon proved $\mathrm{ex}(n,F^t)=\Omega(n^{2-1/\rho})$ for balanced $F$ and $t$ large (lower bound, via the random algebraic method: a random low-degree polynomial over $\mathbb F_q$ defines the extremal graph). They conjectured the matching upper bound $\mathrm{ex}(n,F^t)=O(n^{2-1/\rho})$ for every balanced rooted tree $F$ (their Conjecture 1.4) — if true for all such $F$, this conjecture would trivially imply the full rational exponents conjecture. - The single-graph progress since 2018 is a sequence of papers each proving Conjecture 1.4 for a wider family of rooted trees $F$: Jiang, Ma & Yepremyan (*Combin. Probab. Comput.* 31, 2022); Kang, Kim & Liu, "On the rational Turán exponents conjecture" (*JCTB* 148, 2021, arXiv:1811.06916) — realising $2-a/b$ for $b\equiv\pm1\pmod a$; Conlon, Janzer & Lee (*Combinatorica* 41, 2021); Janzer (*SIAM J. Discrete Math.* 34, 2020); Jiang & Qiu, "Turán numbers of bipartite subdivisions" (2020) and "Many Turán exponents via subdivisions" (arXiv:1908.02385) — realising $1+p/q$ for all $q>p^2$; and Jiang, Jiang & Ma, "Negligible obstructions and Turán exponents" (*Ann. Appl. Math.* 38, 2022) — who studied the specific rooted-tree family $F_{r,s}$ (and its extension $T_{r,s,s'}$) used by Conlon–Janzer, proving Conjecture 1.4 for it under the restrictive condition $r\ge s^3-1$. - The precise rooted tree: $F_{r,s}$ has a center $y$, $r$ middle vertices $z_1,\dots,z_r$ each joined to $y$, and each $z_i$ joined to $s$ leaves $w_{i,1},\dots,w_{i,s}$ (the roots). It is balanced iff $s\le r$, with density $\rho(F_{r,s})=(rs+r)/(r+1)$, giving a lower bound $\mathrm{ex}(n,F_{r,s}^t)=\Omega(n^{2-(r+1)/(rs+r)})$ for $t$ large. - Conlon–Janzer's Theorem 1.5: for all integers $r\ge s+2\ge3$ and $t\ge1$, $\mathrm{ex}(n,F_{r,s}^t)=O(n^{2-(r+1)/(rs+r)})$ — matching the Bukh–Conlon lower bound, under the much weaker hypothesis $r\ge s+2$ (versus Jiang–Jiang–Ma's $r\ge s^3-1$), and with a "considerably simpler" proof (Conlon–Janzer, §1). A companion Theorem 3.1 extends this to the larger tree family $T_{r,s,s'}$ (obtained by attaching $s'$ extra rooted leaves to $y$) under the near-optimal condition $r\ge s-s'+1$. - Converting the tree-power result into Theorem 1.2: a device of Kang, Kim & Liu (arXiv:1811.06916) shows that once exponent $2-a/(ap_0+q)$ is realised by a power of a *balanced rooted graph*, then $2-a/(ap+q)$ is realised for every $p\ge p_0$ — i.e. one balanced-tree witness bootstraps into an infinite family of denominators. Feeding $F_{r,s}$ (with $a=r+1$) through this device is what turns "$\rho(F_{r,s}^t)$ matches for $r\ge s+2$" into the clean closed-form statement "$2-a/b$ realisable for all $b\ge\max(a,(a-1)^2)$." - Confirmed status: published *Advances in Combinatorics* 2022:9 (DOI 10.19086/aic.2022.9), open access, 10 pages; both authors (Conlon, Caltech; Janzer, Trinity College Cambridge) are core contributors to this whole research line (Janzer co-authored several of the predecessor papers above). - The single-graph rational exponents conjecture is still open in full — even combined, the known realisable exponents form a proper, if steadily growing, subset of $\mathbb Q\cap[1,2]$; e.g. erdosproblems.com/571's own literature summary (cross-checked in this wiki's erdos/713.md) lists the fully-general set as still an open target.

Solution

Answer: proved. Every rational $r=2-a/b$ with $b\ge\max(a,(a-1)^2)$ is a Turán exponent of a genuine single graph (not merely a finite family).

The transferable technique — replace Bukh–Conlon's lower-bound tree-power construction with a matching upper bound via a "nice/rich copy" refinement of dependent random choice:

1. Fix the lower bound for free. Bukh–Conlon's Lemma 1.3 already supplies $\mathrm{ex}(n,F^t)=\Omega(n^{2-1/\rho})$ for *any* balanced rooted graph $F$ and $t$ large, via the random algebraic method (random low-degree polynomial over $\mathbb F_q$). This part of the machine is reusable off the shelf; the entire technical burden of every single-graph rational-exponents paper since 2018 — including this one — is proving the matching upper bound for a specific balanced rooted *tree* $F$ (Bukh–Conlon's Conjecture 1.4). The transferable strategic move is: don't attack the conjecture directly — attack it one balanced-tree family at a time, since each solved family yields new closed-form exponents via the Kang–Kim–Liu bootstrap.

2. Reduce to an almost-regular bipartite host graph. Standard reduction (Erdős–Simonovits) lets you assume the $H$-free extremal graph $G$ is $K$-almost-regular (max degree $\le K\cdot$ min degree) and bipartite (Conlon–Lee), turning the problem into: show a bipartite graph with minimum degree $\delta\gtrsim n^{1-(r+1)/(rs+r)}$ must contain $F_{r,s}^t$.

3. Classify stars as "heavy" vs. "light" to kill high-codegree obstructions. An $(s+1)$-star is *heavy* if its leaves have common neighbourhood $\ge|V(H)|$; Lemma 2.2 shows heavy stars are a $o(1)$-fraction of all stars in an $H$-free graph, because a positive density of heavy stars would itself let you embed $H$ (since $F_{r,s}^t$ is a subdivision of an $(s+1)$-partite $(s+1)$-uniform hypergraph). This "heavy/light" dichotomy — controlling codegree via forbidden-subgraph density — traces back to Conlon–Lee and Janzer's earlier work on extremal numbers of subdivisions and now recurs across the whole rational-exponents literature.

4. Call a copy of the tree "nice" if it avoids heavy stars, then show nice copies must be "rich." A nice embedding of $F_{r,s}$ is *(c,k)-rich* if the image of $z_k$ has many neighbours in a carefully defined "common-neighbourhood locus" $S(\cdot)$ built from the other roots' images. The key counting lemma (2.6/2.7) shows: if $G$ is $H$-free and has many nice copies of $F_{r,s}$ sharing the same leaf set, pigeonhole over the bounded number of ways $H=F_{r,s}^t$ could otherwise appear forces many of those copies to collide on an internal vertex — and this collision is exactly what makes them rich (i.e. concentrates many edges into a small locus $X$). - Vertex $v \in Y$ has many neighbours in $X$.

5. Close the loop with a dependent-random-choice-style embedding lemma (Lemma 2.8). Once you have a bipartite subgraph $G[X,Y]$ where a positive-density set of $Y$-vertices each has abnormally large degree into $X$ (more neighbours in $X$ than a random graph of the same density would predict), a short double-counting argument (closely related to, and re-provable via, dependent random choice) forces a copy of $H$ itself — via exactly the same heavy/light star-counting used in step 3, now run in reverse to derive a contradiction. This closes an induction/contradiction cycle: assume $H$-free $\Rightarrow$ derive an unbalanced, over-dense bipartite pattern $\Rightarrow$ that pattern itself forces $H$.

6. Portable takeaway. The technique that "cracked" the exponents near 2 is not a new construction (the algebraic lower bound was already known) — it is a *purely combinatorial, codegree-counting upper-bound technique* (KST-style + heavy/light star classification + "rich copy" collision-forcing) that turns "the graph is $F^t$-free" into "the graph must contain an anomalously dense bipartite pattern," and then re-derives $F^t$ from that pattern. This nice/rich-copy refinement is explicitly noted by the authors to be "considerably simpler" than the prior state of the art (Jiang–Jiang–Ma) while covering a strictly larger parameter range — i.e. the transferable lesson for adjacent open problems is that simplifying the codegree-counting/collision argument, not inventing new algebra, is what extends the realisable-exponent frontier, and the Kang–Kim–Liu bootstrap lemma is the standard device for turning one solved balanced-tree case into an infinite family of closed-form rational exponents.

Related

- erdos/571 — the parent Erdős–Simonovits rational exponents conjecture in its full single-graph form (does every rational $r\in[1,2)$ get realised by a single graph?); this page resolves the sub-range $r$ near 2 in the strong closed form $2-a/b$, $b\ge\max(a,(a-1)^2)$, but the conjecture remains open overall. - Erdős #713 — does every bipartite graph have a Turán exponent? — "does every bipartite graph have a Turán exponent" (existence direction, converse of #571); the same Bukh–Conlon random-algebraic-method + balanced-tree-power toolkit underlies both, and erdos/713.md's own provenance trail independently corroborates this paper's place in the genealogy. - Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — the tree-degenerate Turán conjecture; erdos/146.md explicitly flags this "rational exponents near two" line as a sibling research vein sharing the identical toolkit (random-algebraic lower bounds + dependent-random-choice-style upper bounds) but a formally distinct conjecture. - concept/random-algebraic-method — Bukh–Conlon's random low-degree-polynomial construction; supplies the (already-solved) lower-bound half of every result in this cluster, including this one. - concept/rooted-tree-power-construction — the balanced rooted graph / $t$-blowup framework ($F_{r,s}$, $T_{r,s,s'}$) that is the actual object of study; Conlon–Janzer's contribution is a new, simpler upper-bound proof technique for a wider slice of this family. - 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 standard technique (Fox–Sudakov) for degenerate-graph upper bounds; Conlon–Janzer's Lemma 2.8 is provable directly via dependent random choice (noted explicitly in the paper) and is the engine of the final contradiction step. - concept/kovari-sos-turan-bound — the classical codegree-counting bound whose logic (bound the number of high-codegree stars) is refined here into the heavy/light star dichotomy. - Kahn–Kalai conjecture — threshold vs. expectation-threshold for monotone properties — a structurally distant but methodologically similar recent solved problem: both resolve a hard extremal/threshold statement by finding a single sharper combinatorial statistic (minimum-fragment vs. heavy/light-star-and-rich-copy) that collapses a previously case-heavy argument into a simpler, more portable proof.