Combinatorics Extremal combinatorics Lemma

Szemerédi regularity lemma

Statement

Let $G$ be a finite simple graph with vertex set $V$ . For disjoint nonempty sets $X, Y \subseteq V$ , let $e(X, Y)$ be the number of edges with one end in $X$ and one in $Y$ , and let $d(X, Y) = e(X, Y) / (|X| |Y|)$ . Let $\varepsilon > 0$ . A pair $(A, B)$ of disjoint nonempty sets is $\varepsilon$ -regular if $\abs{d(X, Y) - d(A, B)} \le \varepsilon$ whenever $X \subseteq A$ , $Y \subseteq B$ , $|X| \ge \varepsilon |A|$ and $|Y| \ge \varepsilon |B|$ . A partition $V = V_1 \cup \cdots \cup V_k$ is equitable if any two parts differ in size by at most $1$ .

For every $\varepsilon > 0$ and every integer $m \ge 1$ there is an integer $M = M(\varepsilon, m)$ with the following property. Let $G$ have at least $m$ vertices. Then $G$ has an equitable partition $V_1, \ldots, V_k$ of its vertex set with $m \le k \le M$ . In this partition, all but at most $\varepsilon k^2$ of the pairs $(V_i, V_j)$ with $i < j$ are $\varepsilon$ -regular.

Remarks

The proof uses an energy, the mean square of the densities $d(V_i, V_j)$ , which lies between $0$ and $1$ . If the current partition has too many irregular pairs, the sets $X, Y$ that witness irregularity are used to refine it. Then the energy increases by at least a fixed amount depending on $\varepsilon$ . So the process stops after a bounded number of steps. Each step multiplies the number of parts by an exponential, so $M$ is a tower of exponentials of height polynomial in $1/\varepsilon$ . Gowers showed that bounds of tower type are necessary.

The lemma comes with a counting lemma: if parts $V_1, V_2, V_3$ are pairwise $\varepsilon$ -regular with densities at least $\delta$ and $\varepsilon$ is small compared with $\delta$ , then they span many triangles. Together they prove the triangle removal lemma and the Erdős–Stone theorem.

Going deeper

For a student

The lemma replaces a huge graph by a small weighted "reduced graph" on the parts, with the densities as weights. Questions about copies of a fixed small graph can then be answered in the reduced graph through the counting lemma. This is the route to the triangle removal lemma, to Roth's theorem, and to the Erdős–Stone theorem. Szemerédi first proved a version for bipartite graphs as a step towards Szemerédi's theorem on arithmetic progressions. The limit object of this point of view is the graphon.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`ETMAPNQY7T`
URI	`m2://ETMAPNQY7T`
Kind	statement, lemma
Writing	W0 stub
MSC	05C35, 05D99
Status	This copy of the site has no build data. Run `m2 status ETMAPNQY7T`.
About	Extremal graph theory
Uses	Graph, Partition of a set
Same as	Wikidata Q1295910 Wikipedia Szemerédi regularity lemma
Changed	2 November 2026