Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 13 / 2

For disjoint vertex sets $A,B$, define their edge density of a bipartite graph by $d(A,B)=e(A,B)/(|A||B|)$. They form a regular pair with parameter $\epsilon$ if every $A^{\prime }\subseteq A,B^{\prime }\subseteq B$ with $|A^{\prime }|\ge \epsilon |A|$, $|B^{\prime }|\ge \epsilon |B|$ satisfies $|d(A^{\prime },B^{\prime })-d(A,B)|\le \epsilon$.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and minimum cell count $k_0$, some $K,n_0$ have the following property. Every graph on $n\ge n_0$ vertices admitswith $|V_0|\le \epsilon n$, equal-sized $V_1,\dots ,V_k$, and at most $\epsilon k^2$ unordered irregular pairs. It is enough to consider $0<\epsilon <1/2$.

Prove this using equitable regularity energy. Treat exceptional vertices as singleton cells and setwith ordered pairs and the adjacency indicator also defining diagonal densities. Then $0\le q\le 1$. The refinement variance identity for regularity energy proves refinement cannot decrease $q$:An irregular pair supplies witness subsets of relative sizes at least $\epsilon$ whose density differs by more than $\epsilon$. Refining along those witnesses raises $q$ by more than ${\epsilon }^4{L}^2/n^2$ per orientation, where $L$ is the common cell size. If there are more than $\epsilon k^2$ irregular pairs, the increase is greater than ${\epsilon }^5(kL/n{)}^2\ge {\epsilon }^5/4$, provided the exceptional set has size at most $n/2$.

Refine each cell by all its witness subsets; this produces at most $2^k$ atoms per cell. Restore equal sizes by the equalization with a controlled exceptional set: cut each atom into blocks of size $\lfloor L/4^k\rfloor$ and declare its remainder exceptional, still retaining every such vertex as a singleton in the energy. This is another refinement, so no energy is lost. At most $k{2}^k\lfloor L/4^k\rfloor \le n{2}^{-k}$ vertices become exceptional, and, when $L\ge 2\cdot 4^k$, at most $2k{4}^k$ new nonexceptional cells occur.

Put $T=\lceil 4{\epsilon }^{-5}\rceil$ and start with $k\ge k_0$ so large that $T{2}^{-k}\le \epsilon /2$. An initial equitable partition has at most $\epsilon n/2$ exceptional vertices when $n$ is sufficiently large. Subsequent cell counts only increase, so the total added exceptional set has size at most $\epsilon n/2$. The recurrence $k\mapsto 2k{4}^k$, iterated at most $T$ times, supplies a finite bound $K$; choose $n_0$ large enough that every intermediate $L$ meets the size requirement. More than $T$ unsuccessful refinements would raise $q$ above one. The process must therefore stop with the required regular pairs. This proves the lemma.

Its usefulness comes from replacing an arbitrarily large graph by the bounded reduced graph of a regularity partition. For fixed positive cross-density, the graph embedding lemma for regular pairs lifts fixed configurations from the reduced graph to the original one. In particular, three sufficiently regular positive-density pairs contain many triangles in a graph. Deleting exceptional, intracell, irregular and sparse-pair edges then gives the triangle removal lemma: a graph with sufficiently few triangles can be made triangle-free by deleting $o(n^2)$ edges. A triangle surviving in the reduced graph would force a positive proportion of the original possible triangles, a contradiction. More generally this approach yields the clique removal lemma and the asymptotic Erdős-Stone theorem. Applied to the tripartite graph encoding $x+z=2y$, triangle removal also gives Roth theorem on three-term arithmetic progressions. The price is that the energy argument gives a very rapidly growing, iterated-exponential bound on $K(\epsilon )$; the lemma is a structural tool, not a promise of small practical constants.