Szemerédi regularity lemma

For every $\epsilon >0$ and $m_0$ there are $M,n_0$ such that every graph on at least $n_0$ vertices has a partitionwhere $m_0\le m\le M$, $|V_0|\le \epsilon |V|$, the other parts have equal size, and all but at most $\epsilon m^2$ pairs $(V_i,V_j)$ are $\epsilon$-regular.

For every $\epsilon >0$, all sufficiently large finite graphs admit a set partition into at most $M(\epsilon )$ nonempty cells, each of size at most $\epsilon n$, with the displayed ordered irregular-pair weight bound. Start with small cells. Use regularity energy including diagonal rectangles, refine simultaneously by the witness subsets of all irregular pairs, and apply the refinement variance identity for regularity energy. Each failing round raises energy by more than ${\epsilon }^5$, while energy lies in $[0,1]$. The recurrence $k\mapsto k{2}^k$ bounds the final cell count. Equitability is unnecessary for this weighted version.

A partition with at most $M$ cells has at most $\epsilon n$ vertices in cells smaller than $\epsilon n/M$. Deleting all edges incident to those vertices costs at most $\epsilon n^2$ edges. Every remaining cell has a fixed positive fraction of all vertices, which permits a regular triangle counting lemma to give a cubic count without requiring equal cell sizes.

Use equitable regularity energy with exceptional vertices retained as singleton cells. The refinement variance identity for regularity energy shows that splitting along an irregular pair's witnesses raises energy by more than ${\epsilon }^4|V_i||V_j|/n^2$. More than $\epsilon k^2$ irregular ordered pairs therefore raise energy by more than ${\epsilon }^5/4$ when the exceptional set occupies at most half the vertices.

For equalization with a controlled exceptional set, cut each of the at most $k{2}^k$ witness atoms into pieces of size $\lfloor L/4^k\rfloor$ and put leftovers into singleton exceptional cells. This is a refinement, so it cannot decrease energy. At most $n{2}^{-k}$ vertices are lost. Start with enough cells that this loss, over $\lceil 4{\epsilon }^{-5}\rceil$ rounds, is at most $\epsilon n/2$; the initial exceptional set uses the other half. The number of cells grows by a bounded recurrence depending only on $\epsilon$ and the prescribed minimum. Energy lies in $[0,1]$, so the process terminates.

For fixed forbidden induced patterns, a regularity and Ramsey refinement uses internal clique/independent types and sparse, almost-complete, or intermediate cross pairs. A clique of intermediate pairs realizes every bounded induced pattern consistent with those internal types, using both edge and nonedge regularity. This is the induced embedding consequence used in hereditary graph enumeration theorem; the exceptional-pair budget can be arbitrarily small.

For fixed $r\ge 2$ and every $\epsilon >0$, some $\delta >0$ has the following property for all sufficiently large $n$: a graph with fewer than $\delta n^r$ copies of $K_r$ can be made $K_r$-free by deleting at most $\epsilon n^2$ edges. A Szemerédi regularity lemma partition and the regular clique counting lemma prove this. It converts sparse counts of a forbidden clique into a small edit distance from clique-freeness.

For every $\eta >0$, some $\rho >0$ and $N_0$ have this property: a graph on $N\ge N_0$ vertices with fewer than $\rho N^3$ unordered triangles in a graph can be made triangle-free by deleting at most $\eta N^2$ edges. A Szemerédi regularity lemma partition deletes exceptional, intraclass, irregular and sparse-pair edges cheaply. A surviving triangle in a graph would force a positive cubic count by the regular triangle counting lemma.

For a set partition $\mathcal{P}$ of the vertices of a graph of order $n$, definewhere the sum is ordered, the adjacency indicator defines the density also on diagonal pairs, and exceptional vertices are treated as singleton parts. Refinement cannot decrease this energy, by the Cauchy-Schwarz inequality. An irregular pair of equal cells of size $m$, with witnesses of relative size at least $\epsilon$ and density discrepancy greater than $\epsilon$, increases the energy by more than ${\epsilon }^4{m}^2/n^2$ for each orientation. Splitting refined atoms into equal chunks and leftover singleton parts is a further refinement, so restoring equitability causes no energy loss.

In a proof of the Szemerédi regularity lemma, suppose $k$ equal classes have size $L$ and witness splitting creates at most $2^k$ atoms per class. Divide every atom into blocks of size $\ell =\lfloor L/4^k\rfloor$, putting leftovers into the exceptional set. At most $k{2}^k\ell \le kL{2}^{-k}$ vertices are lost. When $L\ge 2\cdot 4^k$, at most $2k{4}^k$ blocks remain. For equitable regularity energy defined by omitting exceptional vertices, the loss from discarding a fraction $r$ is at most $2r$: only ordered pairs incident with discarded vertices are removed, and every squared edge density of a bipartite graph is at most one. This provides a quantitative way to restore equal class sizes after each energy increment.

If a set partition refines a rectangle $U\times V$ of a graph into rectangles $U_a\times V_b$, write $d=d(U,V)$ for its edge density of a bipartite graph. The weighted variance identity isIt follows by expanding the square and using ${\sum }_{a,b}|U_a||V_b|d(U_a,V_b)=|U||V|d$. In particular, equitable regularity energy cannot decrease under refinement. If a witness rectangle has relative sizes at least $\epsilon$ and edge density of a bipartite graph discrepancy greater than $\epsilon$, its contribution, after division by the squared total vertex count, exceeds ${\epsilon }^4|U||V|/N^2$.