Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983)

Statement

Setup. For a graph (or, more generally, an $r$-uniform hypergraph) $H$ on $h$ vertices, let $\mathrm{ex}(n,H)$ be the Turán number (maximum edges in an $n$-vertex $H$-free graph) and $\pi(H) = \lim_{n\to\infty} \mathrm{ex}(n,H)/\binom{n}{2}$ the Turán density. A graph $G$ with more than $\mathrm{ex}(n,H)$ edges is called supersaturated (Erdős–Simonovits, "Supersaturated graphs and hypergraphs," *Combinatorica* 3 (1983), 181–192, per Springer/Semantic Scholar listing) — by definition it must contain *at least one* copy of $H$, and the paper's basic question is: how many copies of $H$ are forced once $e(G)$ exceeds $\mathrm{ex}(n,H)$ by a given excess $k$?

Supersaturation Theorem (qualitative, modern $\pi(H)$-normalized form). For every graph $H$ on $h$ vertices and every $\varepsilon>0$ there is $\delta=\delta(H,\varepsilon)>0$ such that: if $G$ is an $n$-vertex graph with $$e(G)\ \ge\ (\pi(H)+\varepsilon)\binom{n}{2},$$ then $G$ contains at least $\delta n^h$ copies of $H$ (A. G. Thomason, Part III Extremal Graph Theory lecture notes, Cambridge — WebSearch-snippet-sourced statement).

Worked clique case (Erdős–Simonovits, quantitative). For $H=K_{k+1}$, $\pi(K_{k+1})=1-1/k$ (Turán's theorem), and the supersaturation bound is explicit: if $e(G)\ge(1-\tfrac1k+\varepsilon)\tfrac{n^2}2$, then $G$ contains $\Omega_{k,\varepsilon}(n^{k+1})$ copies of $K_{k+1}$ — i.e. once you cross the Turán threshold by any fixed $\varepsilon$, the number of forced cliques is a positive-density fraction of all possible $(k{+}1)$-subsets, not merely "at least one." A companion stability refinement for $k=2$ (Lovász–Simonovits) sharpens this near the threshold itself: if $G$ has $\lfloor n^2/4\rfloor+t$ edges but *fewer* than $C|t|n$ triangles, then $O(|t|)$ edges can be deleted from $G$ to make it triangle-free (bipartite) — i.e. *few* triangles forces near-bipartiteness, the contrapositive-flavored partner of the supersaturation count (WebSearch-aggregated summary).

The 1984 sequel, "Cube-Supersaturated Graphs and Related Problems" (Erdős–Simonovits, in *Progress in Graph Theory*, Waterloo 1982, Academic Press 1984, 203–218) applies the same idea to *degenerate* bipartite $H$ (where $\pi(H)=0$, so the theorem above is vacuous and a different, sharper $n^{2-1/r}$-type analysis is needed) — it is the origin paper for this wiki's Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021, Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$, Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ (degenerate-bipartite Turán conjectures) and Erdős #713 — does every bipartite graph have a Turán exponent? (hypercube $Q_3$ Turán exponent).

Facts

- Origin and exact question. Erdős–Simonovits 1983 fix a forbidden family $\mathcal L$, define $\mathrm{ex}(n,\mathcal L)$, call $G$ supersaturated once $e(G)>\mathrm{ex}(n,\mathcal L)$, and ask: at least how many copies of $L\in\mathcal L$ must occur once $G$ has $\mathrm{ex}(n,\mathcal L)+k$ edges, as a function of $k$ and $n$ (Combinatorica 3 (1983) 181–192, per Semantic Scholar/Springer listing). - **This is the general engine behind Turán-type *stability* theorems**: a graph with edge count just above $\mathrm{ex}(n,H)$ is not merely non-$H$-free but forced to contain *many* copies, and — via the companion stability direction (few copies $\Rightarrow$ structurally close to the extremal configuration) — this pins down the *approximate shape* of near-extremal graphs, not just their edge count. - Historical pipeline to Roth's theorem. Ruzsa and Szemerédi's (6,3)-theorem (1976/78) is a supersaturation-flavored statement about triangles in tripartite graphs that yields the triangle removal lemma, which in turn gives a purely combinatorial proof of Roth's theorem on 3-term arithmetic progressions (en.wikipedia.org/wiki/Graph_removal_lemma, directly fetched) — the historically first instance of the "supersaturation $\to$ removal lemma $\to$ additive-combinatorics theorem" pipeline that this wiki's Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems page documents in its generalized (Szemerédi/multidimensional) form. - Removal lemma is the size/quantifier-dual partner, not a synonym. The graph removal lemma (generalized to $r$-uniform hypergraphs by Erdős–Frankl–Rödl 1986; modern graph-only formulation first stated by Füredi 1994) says: for every $\varepsilon>0$ there is $\delta(\varepsilon,H)>0$ such that fewer than $\delta n^h$ copies of $H$ $\Rightarrow$ can delete $\le\varepsilon n^2$ edges to kill them all. Supersaturation runs the same quantifiers in the other direction: density above $\pi(H)+\varepsilon$ $\Rightarrow$ at least $\delta n^h$ copies. Contrapositively they interlock (few copies $\Leftrightarrow$ can't be dense above $\pi(H)$ without near-total removal), but the removal lemma's $\delta(\varepsilon)$ dependence proved via Szemerédi-regularity compactness is typically astronomically worse (tower-type, per this wiki's Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems page) than the $\delta$ obtainable by a direct supersaturation-style counting argument for a fixed pattern $H$. - Balanced supersaturation is a structural strengthening — not just "many copies of $H$" but "many copies that are *spread out*, no small vertex subset hosting too large a share" — used as the key combinatorial input to the hypergraph container method (Balogh–Morris–Samotij; Saxton–Thomason) for counting the number of $H$-free graphs/hypergraphs asymptotically and for transferring Turán-type extremal results to sparse random-graph settings (the Kohayakawa–Łuczak–Rödl-conjecture-type transference results) — see e.g. arXiv:1707.03788 "Balanced supersaturation for some degenerate hypergraphs" (title/abstract-level, not primary-read in this session). - This wiki's own worked example: Grzesik–Janzer–Nagy (arXiv:1904.07219, cited on Turán and Sidorenko bounds for tree-degenerate bipartite graphs (Grzesik–Janzer–Nagy 2019; Jiang–Longbrake 2022)) prove $\mathrm{ex}(n;H)=O(n^{2-1/r})$ for $r$-degenerate blow-ups of trees by combining supersaturation with a random walk on an auxiliary graph — a direct illustration of supersaturation being used not as the final theorem but as an intermediate lemma feeding a further combinatorial argument. - Erdős's own double-counting/Ramsey use (this wiki's Erdős #838 — f(n), the minimum number of distinct convex subsets of n points (open precise growth rate; two-sided quasi-polynomial bound SOLVED by Erdős 1978 via double counting against the Erdős–Szekeres theorem)): forcing many distinct copies of a Ramsey-guaranteed substructure by double-counting (subset, copy) incidence pairs is explicitly flagged there as "a supersaturation-style argument built entirely from elementary double counting" that transfers to any "minimum number of distinct forced substructures" question once a matching Ramsey/extremal theorem is already known — i.e. the supersaturation *pattern of argument* (threshold-crossing forces abundance) recurs even where the formal Erdős–Simonovits theorem statement isn't directly invoked.

Technique

WHEN it applies. - You already know (or can cite) the exact or asymptotic Turán number/density $\mathrm{ex}(n,H)$ or $\pi(H)$ for a fixed pattern $H$, and you need to upgrade a *qualitative* "some graph denser than extremal must contain $H$" fact into a *quantitative* "abundantly many copies" fact. - You need the abundance conclusion as an intermediate lemma, not the final goal — typically to feed one of: (a) a deletion/iteration argument (find a copy, delete a vertex/edge from it, repeat, using that there are still "enough" copies left after each deletion — this is exactly the random-walk-plus-supersaturation shape of the Grzesik–Janzer–Nagy proof on Turán and Sidorenko bounds for tree-degenerate bipartite graphs (Grzesik–Janzer–Nagy 2019; Jiang–Longbrake 2022)); (b) a stability theorem (near-extremal graphs are structurally close to the extremal examples) via the contrapositive "few copies $\Rightarrow$ near-extremal structure" direction; (c) the removal-lemma pipeline into Ramsey/density theorems for arithmetic progressions or other combinatorial patterns (Roth, corners, Szemerédi — see Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems); (d) the container method for counting $H$-free graphs/hypergraphs and for transference to sparse random settings, where the *balanced* refinement (spread-out copies, not just many copies) is the load-bearing structural fact. - It does not by itself resolve what $\mathrm{ex}(n,H)$ or $\pi(H)$ *is* — supersaturation is downstream of an extremal-number result, not a replacement for one, and for degenerate patterns ($\pi(H)=0$) the $\pi(H)$-normalized statement above is vacuous, forcing a different (typically $n^{2-1/r}$-type) supersaturation analysis, which is exactly the regime of the 1984 Erdős–Simonovits "Cube-Supersaturated Graphs" sequel and of Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021/Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$/Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$.

WHY it works (the mechanism). - Averaging/embedding proof of the qualitative bound. The standard route (Thomason's Cambridge Part III notes) embeds $G$ into a large auxiliary "host": partition (or randomly map) $V(G)$ into $h$-tuples covering many potential copies of $H$, and use that once the *local* density on a sub-instance exceeds $\pi(H)+\varepsilon$, it individually can't be $H$-free (since $\pi(H)$ is by definition the supremum density of an $H$-free graph) — the excess $\varepsilon$ over the exact asymptotic threshold is precisely what prevents *every* sub-instance from simultaneously dodging $H$; averaging this pigeonhole conclusion over polynomially many sub-instances converts "at least one copy exists somewhere" into "$\Omega(n^h)$ copies exist overall." - Compactness/regularity proof of the qualitative bound (equivalent to the removal lemma route). Abstractly: if the theorem failed, a sequence of counterexample graphs $G_n$ with density $\ge\pi(H)+\varepsilon$ but $o(n^h)$ copies of $H$ would, via Szemerédi-regularity/graphon compactness, converge to a limit object with density $\ge\pi(H)+\varepsilon$ and *zero* $H$-density — contradicting the very definition of $\pi(H)$ as the supremum density achievable while staying $H$-free. This is the same compactness mechanism this wiki's Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems page documents for the graph/hypergraph removal lemma, and it is why supersaturation and the removal lemma are usually proved (and taught) side by side even though their quantifier directions differ. - Why the excess $\varepsilon$ is essential, not cosmetic. Exactly *at* the threshold $e(G)=\mathrm{ex}(n,H)$, $G$ can still be $H$-free by definition — supersaturation is a genuinely different, harder statement than the Turán theorem itself: it says the extremal examples are *isolated* in density-space, and stepping even a fixed $\varepsilon$ away from them costs you $H$-freeness so badly that you get a whole polynomial-order family of copies, not just a single one. This "isolation of extremal configurations" is the real content re-used across every application above (stability, deletion arguments, container method). - Recombination pattern for solving a new problem: (1) pin down or cite $\mathrm{ex}(n,H)$/$\pi(H)$; (2) invoke (or reprove, via the averaging or compactness argument above) supersaturation to get $\ge\delta n^h$ copies once density exceeds the threshold by $\varepsilon$; (3) feed that abundance into whichever downstream engine the target problem needs — deletion/iteration for a Turán bound on a *related*, more complex pattern (as in Turán and Sidorenko bounds for tree-degenerate bipartite graphs (Grzesik–Janzer–Nagy 2019; Jiang–Longbrake 2022)), a stability argument for structural classification, or the removal-lemma/regularity machinery for a density/Ramsey-type arithmetic theorem.

Related

- Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems — the graph/hypergraph removal lemma and Gowers-uniformity density-increment strand; the removal lemma is supersaturation's quantifier-dual partner, and both share the same Szemerédi-regularity/graphon-compactness proof mechanism; this is the pipeline used for Roth's theorem, the corners theorem, and Szemerédi's theorem. - Erdős #113 — bipartite ex(n,G)≪n^{3/2} iff 2-degenerate: DISPROVED by Janzer 2021 — Erdős–Simonovits's disproved conjecture on bipartite $\mathrm{ex}(n,G)\ll n^{3/2}$ iff 2-degenerate, originating in the same 1983/84 supersaturation-paper lineage ([ErSi84]). - Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — the still-open general $r$-degenerate $\Rightarrow \mathrm{ex}(n,H)\ll n^{2-1/r}$ conjecture, same origin. - Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ — the disproved companion min-degree-$r$ lower-bound conjecture, same origin. - Erdős #713 — does every bipartite graph have a Turán exponent? — hypercube Turán exponent question, whose reference paper is literally titled "Cube-Supersaturated Graphs and Related Problems" (Erdős–Simonovits 1984). - Erdős #838 — f(n), the minimum number of distinct convex subsets of n points (open precise growth rate; two-sided quasi-polynomial bound SOLVED by Erdős 1978 via double counting against the Erdős–Szekeres theorem) — Erdős's minimum-number-of-convex-subsets problem, whose solved two-sided bound uses "a supersaturation-style argument built entirely from elementary double counting" against the Erdős–Szekeres theorem, illustrating the same abundance-from-threshold-crossing pattern outside the Turán-number setting. - Turán and Sidorenko bounds for tree-degenerate bipartite graphs (Grzesik–Janzer–Nagy 2019; Jiang–Longbrake 2022) — Grzesik–Janzer–Nagy's proof of $\mathrm{ex}(n;H)=O(n^{2-1/r})$ for $r$-degenerate tree blow-ups, which combines supersaturation with a random-walk argument on an auxiliary graph — a worked example of supersaturation as an intermediate lemma rather than the final theorem.