Turán number ex(n,H): extremal edge-count for forbidden subgraphs

Statement

For a graph (or family of graphs) $H$, the Turán number (extremal number) is $$\mathrm{ex}(n,H) \;=\; \max\{\, e(G) : |V(G)|=n,\ G \text{ contains no subgraph isomorphic to } H \,\}.$$ It is the central quantity of extremal graph theory: the maximum number of edges an $n$-vertex graph can have while forbidding $H$ as a (not necessarily induced) subgraph (en.wikipedia.org/wiki/Extremal_graph_theory).

Turán's theorem (1941). For $H=K_{r+1}$, the unique extremal graph is the Turán graph $T(n,r)$ — the complete $r$-partite graph on $n$ vertices with balanced part sizes $\lceil n/r\rceil$ or $\lfloor n/r\rfloor$ — and $$\mathrm{ex}(n,K_{r+1}) = e(T(n,r)) = \left(1-\frac1r\right)\frac{n^2}{2} + O(1).$$ The case $r=2$ ($H=K_3$, triangle) is Mantel's theorem (1907): $\mathrm{ex}(n,K_3)=\lfloor n^2/4\rfloor$, achieved by the balanced complete bipartite graph $K_{\lceil n/2\rceil,\lfloor n/2\rfloor}$ (en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem).

Erdős–Stone theorem (1946), "the fundamental theorem of extremal graph theory": for any fixed $H$ with chromatic number $\chi(H)=r>2$, $$\mathrm{ex}(n,H) = \left(\frac{r-2}{r-1}+o(1)\right)\binom n2,$$ i.e. asymptotically the same edge density as $T(n,r-1)$ (en.wikipedia.org/wiki/Erdős–Stone_theorem). Equivalently the Turán density $\pi(H) := \lim_{n\to\infty}\mathrm{ex}(n,H)/\binom n2$ exists and equals $\tfrac{r-2}{r-1}$ — it depends on $H$ *only* through $\chi(H)$, so Erdős–Stone (with Erdős–Simonovits's refinement) completely settles the first-order asymptotics of $\mathrm{ex}(n,H)$ for every non-bipartite $H$.

The degenerate case ($\chi(H)=2$, i.e. $H$ bipartite) is where Erdős–Stone gives only the trivial $\mathrm{ex}(n,H)=o(n^2)$, and pinning down the exact polynomial exponent is a deep, largely open research program (en.wikipedia.org/wiki/Erdős–Stone_theorem; arxiv.org/abs/1306.5167). Two landmark results here:

- Kővári–Sós–Turán theorem (1954): for the complete bipartite graph $K_{s,t}$ ($s\le t$), $$\mathrm{ex}(n,K_{s,t}) = O\!\left(n^{2-1/s}\right),$$ proved by double-counting "cherries" (paths of length 2) and a convexity/Jensen argument on vertex codegrees: if too many edges are present, some $s$-subset of vertices has $\ge t$ common neighbors, forcing a $K_{s,t}$ (en.wikipedia.org/wiki/Kővári–Sós–Turán_theorem). This bound is conjectured tight ($\mathrm{ex}(n,K_{s,t})=\Theta(n^{2-1/s})$) for $t$ sufficiently large relative to $s$; matching lower bounds come from algebraic constructions — projective-plane/affine-space incidence graphs for small cases, and norm graphs (Kollár–Rónyai–Szabó; Alon–Rónyai–Szabó) in general. - Bondy–Simonovits (even-circuit) theorem (1974): for even cycles, $$\mathrm{ex}(n,C_{2k}) = O\!\left(n^{1+1/k}\right),$$ first stated (without proof) by Erdős in 1964; Bondy–Simonovits also showed any graph with $\Omega(n^{1+1/k})$ edges contains cycles of *every* even length between $2k$ and $2kn^{1/k}$ (en.wikipedia.org/wiki/Even_circuit_theorem). Tightness ($\Theta(n^{1+1/k})$) is proven only for $k=2,3,5$ ($\mathrm{ex}(n,C_4)=\Theta(n^{3/2})$, $\mathrm{ex}(n,C_6)=\Theta(n^{4/3})$, $\mathrm{ex}(n,C_{10})=\Theta(n^{6/5})$, via generalized-polygon incidence graphs); the general Erdős–Simonovits girth conjecture that this holds for every $k$ remains open.

Facts

- Zarankiewicz problem equivalence: Kővári–Sós–Turán is literally a bound on the Zarankiewicz function $z(m,n;s,t)$ = max edges in an $m\times n$ bipartite graph with no $K_{s,t}$; $\mathrm{ex}(n,K_{s,t})$ for general graphs and $z(n,n;s,t)$ for bipartite host graphs are the same problem up to constants (en.wikipedia.org/wiki/Kővári–Sós–Turán_theorem). - Supersaturation (Erdős–Simonovits, 1983): once $e(G) > (1+\varepsilon)\,\mathrm{ex}(n,H)$, $G$ contains not just one but $\Omega(n^{|V(H)|})$ copies of $H$ — this "excess edges force many copies, not just one" principle is the standard bridge from extremal *edge-counting* bounds to *counting/embedding* results, and is the engine behind proofs like Grzesik–Janzer–Nagy's tree-blow-up Turán bound (arXiv:1904.07219, cited in this wiki's problems/146.md and problems/tree-degenerate-graphs-turan.md). - Erdős–Simonovits stability theorem: for non-bipartite $H$ with $\chi(H)=r$, any $H$-free $G$ with $e(G) = (1-o(1))\,\mathrm{ex}(n,H)$ must be *structurally* close to $T(n,r-1)$ — obtainable from it by adding/deleting $o(n^2)$ edges. This "near-extremal graphs are near-Turán-graphs" principle is one of the most-reused facts in the field. - The general degenerate/bipartite regime is the frontier: while non-bipartite $H$ is essentially fully understood via Erdős–Stone(–Simonovits), pinning the exact exponent for bipartite $H$ — e.g. the Erdős–Simonovits conjecture that $r$-degenerate bipartite $H$ forces $\mathrm{ex}(n,H)=O(n^{2-1/r})$ — is open (Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, \$500 prize, open since 1967/1984; this wiki's problems/146.md). - Adjacent conjectures in the same $r$-degenerate program have been disproved, showing the landscape is *not* monotone in the naive way: Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 (the biconditional "$\mathrm{ex}(n,G)\ll n^{3/2}\iff G$ 2-degenerate") was disproved by Oliver Janzer (arXiv:2109.06110, 2021/2023) via an explicit 3-regular bipartite counterexample, and independently by Dong–Gao–Liu (arXiv:2501.12953, 2025) via graph-gluing — both papers directly manipulate Turán numbers of bipartite graphs as their core object. - Solved special case: for tree-degenerate bipartite graphs (a structured sub-family of $r$-degenerate bipartite graphs), the sharp bound $\mathrm{ex}(n,H)=O(n^{2-1/r})$ *is* proven — Grzesik–Janzer–Nagy 2019 (arXiv:1904.07219, blow-ups of trees, via supersaturation + a random walk on an auxiliary graph) and Jiang–Longbrake 2022 (arXiv:2201.10699, "nested dependent random choice", also links to Sidorenko's conjecture) — documented in this wiki's problems/tree-degenerate-graphs-turan.md. - Kővári–Sós–Turán-style double counting recurs as a plug-in tool outside pure Turán-number questions: e.g. T. D. Parsons's 1975 upper bound on the Ramsey number $R(C_4,S_n)$ (Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n?) is exactly a KST-type double-count of paths of length 2, bounding the max degree of a $C_4$-free graph, with matching lower bounds from the Erdős–Rényi/Brown polarity graph of $\mathrm{PG}(2,q)$ (this wiki's problems/552.md). - Canonical survey: Füredi & Simonovits, "The history of degenerate (bipartite) extremal graph problems," in *Erdős Centennial* (Bolyai Society Math. Studies 25), Springer, 2013, arXiv:1306.5167 — the standard reference tracing Kővári–Sós–Turán, Bondy–Simonovits, Zarankiewicz, and the whole degenerate-Turán research program from origin to (2013-era) state of the art.

HOW $\mathrm{ex}(n,H)$ is used to prove things (recombination steps)

1. Reduce a combinatorial/number-theoretic question to "does a graph avoiding $H$ have too many edges?" Many extremal problems (Ramsey numbers, sum-free/covering-density bounds, incidence bounds in finite geometry) can be recast as: build an auxiliary graph $G$ encoding the structure of interest, note that a forbidden configuration corresponds to a copy of some $H$ in $G$, then bound $e(G)$ via $\mathrm{ex}(n,H)$. (This wiki's Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n? / problems/552.md is a worked instance: bounding $R(C_4,S_n)$ reduces to bounding the max degree of a $C_4$-free graph, i.e. essentially $\mathrm{ex}(n,C_4)=\Theta(n^{3/2})$.) 2. Classify $H$ by chromatic number first. If $\chi(H)>2$, Erdős–Stone(–Simonovits) *immediately* gives the first-order answer $\pi(H)=\frac{\chi(H)-2}{\chi(H)-1}$ — no further work needed for the leading term; remaining work (if any) is the lower-order $o(n^2)$ correction. If $\chi(H)=2$ (bipartite), Erdős–Stone gives nothing beyond $o(n^2)$ and you must go to degenerate-case machinery. 3. In the degenerate/bipartite case, match upper and lower bounds separately — they use disjoint toolkits: - *Upper bounds* on $\mathrm{ex}(n,H)$: double-counting / Kővári–Sós–Turán-style codegree arguments (works cleanly for complete bipartite $H=K_{s,t}$ and generalizes via dependent random choice to broader bipartite/degenerate families — this is exactly the move in Grzesik–Janzer–Nagy and Jiang–Longbrake's proofs of special cases of Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$). - *Lower bounds* (matching constructions): algebraic/finite-geometry constructions — incidence graphs of projective planes or generalized polygons (giving the $k=2,3,5$ tight cases of Bondy–Simonovits), norm graphs (Kollár–Rónyai–Szabó, Alon–Rónyai–Szabó) for general $K_{s,t}$, or random-algebraic constructions (Bukh–Conlon) for the rational-exponents program. A gap between the KST-type upper bound and the best known algebraic lower bound is exactly what leaves a Turán-number problem *open* (as with Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$'s general case, still stuck at Alon–Krivelevich–Sudakov's weaker $O(n^{2-1/(4r)})$ for general $r$). 4. Use supersaturation to upgrade an edge-count bound into a counting/embedding statement. Once $e(G)>(1+\varepsilon)\,\mathrm{ex}(n,H)$ is known, supersaturation automatically gives $\Omega(n^{|V(H)|})$ copies of $H$, not just $\ge 1$ — the standard next step whenever a problem needs "many" copies of a structure rather than a bare existence result. 5. Use the Erdős–Simonovits stability theorem to pin down near-extremal structure, not just the count — useful whenever the *proof* of a downstream result needs to know that an $H$-free graph with close-to-maximum edges must look like (a perturbation of) $T(n,\chi(H)-1)$. 6. Know the ceiling: for bipartite $H$, matching the KST-type upper-bound exponent with an explicit algebraic construction is often the entire difficulty of the problem — when that gap cannot be closed, the honest state is "open," as documented for the general case of Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ and the Erdős–Simonovits girth conjecture for general even cycles.

WHEN it applies: any problem where the object of interest can be encoded as "does a graph (or hypergraph) on $n$ ground elements avoid a fixed small pattern $H$" — Ramsey-type upper bounds via auxiliary $H$-free graphs, incidence bounds in combinatorial geometry, bounds on distinct sums/differences or arithmetic patterns recast as graph problems, and directly any question phrased as $\mathrm{ex}(n,H)$ or a bipartite/degenerate variant thereof.

WHY it works (the mechanism): for non-bipartite $H$, the Turán graph $T(n,\chi(H)-1)$ is *simultaneously* (a) provably $H$-free (any $\chi(H)-1$-partite graph cannot contain a graph needing $\chi(H)$ colors) and (b) edge-maximal among such graphs by an averaging/edge-switching argument (Zykov symmetrization / Motzkin–Straus-style), so upper and lower bounds meet exactly and only the chromatic number matters — this is the deep reason Erdős–Stone reduces an apparently graph-specific question to one integer invariant. For bipartite $H$, this coincidence breaks: there is no analogous "canonical extremal graph" template, so upper bounds must be extracted by a genuinely different, more local mechanism (double-counting incidences at each vertex/codegree, à la Kővári–Sós–Turán) while lower bounds require bespoke algebraic pseudorandom constructions whose edge distribution is provably not concentrated the way KST's convexity argument would need for a matching bound — the resulting *gap* between these two independently-derived bounds is the generic open-problem shape of the field (documented concretely in Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$).

Related

- Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — Erdős–Simonovits conjecture that $r$-degenerate bipartite $H$ forces $\mathrm{ex}(n,H)=O(n^{2-1/r})$; open since 1967/1984, \$500 prize; the general open frontier of this exact concept. - Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 — related biconditional (2-degenerate $\iff$ $\mathrm{ex}(n,G)\ll n^{3/2}$), disproved by Janzer (arXiv:2109.06110) and independently by Dong–Gao–Liu (arXiv:2501.12953), both via explicit Turán-number-bounding constructions. - Erdős #552 — Ramsey number R(C4,Sn), dip below n+√n? — Ramsey number $R(C_4,S_n)$; upper bound is a direct Kővári–Sós–Turán-style double-counting argument (Parsons 1975), lower bound from the polarity-graph construction that also witnesses $\mathrm{ex}(n,C_4)=\Theta(n^{3/2})$. - Sieve theory: Eratosthenes–Legendre, Brun, Selberg, Turán, and the large sieve — Turán's *sieve* (1934) is a historically and terminologically distinct construction by the same mathematician (Pál Turán); it is a second-moment counting technique in analytic number theory, unrelated in mechanism to the Turán *number*/extremal-graph-theory concept documented on this page, despite the shared name. - problems/tree-degenerate-graphs-turan.md (solved/tree-degenerate-graphs-turan) — the solved tree-degenerate special case of Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, via supersaturation (Grzesik–Janzer–Nagy, arXiv:1904.07219) and nested dependent random choice (Jiang–Longbrake, arXiv:2201.10699).