Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 88 / 3

For disjoint nonempty vertex sets $U,V$, write $d(U,V)=e(U,V)/(|U||V|)$. A regular pair of vertex sets is $\epsilon$-regular if every $U^{\prime }\subseteq U,V^{\prime }\subseteq V$ with $|U^{\prime }|\ge \epsilon |U|$, $|V^{\prime }|\ge \epsilon |V|$ satisfies $|d(U^{\prime },V^{\prime })-d(U,V)|\le \epsilon$.

The Szemerédi regularity lemma states that, for every $\epsilon >0$ and integer $m_0$, there are $M,n_0$ such that every finite simple graph on $n\ge n_0$ vertices has a set partitionwith $m_0\le m\le M$, $|V_0|\le \epsilon n$, $|V_1|=\cdots =|V_m|$, and at most $\epsilon m^2$ irregular unordered pairs among the nonexceptional classes. Prove it for $0<\epsilon \le 1/2$; larger parameters follow by using a smaller one.

For the energy-increment proof of Szemerédi regularity, keep every exceptional vertex as a singleton cell in the set partition used to measure regularity energy. Define the equitable regularity energyThe sum is ordered, and on diagonal cells subset density means the average of the adjacency indicator, with zero on loops. Thus $0\le q\le 1$. If $U,V$ are refined into $U_a,V_b$, expanding squares givesThe cross term vanishes because the weighted arithmetic mean of the refined subset densities is the original subset density. Consequently every refinement of a set partition increases or preserves regularity energy.

Suppose the current nonexceptional classes have common size $t$ and there are $k$ of them. For each irregular pair $V_i,V_j$, choose witnesses $A_{ij},B_{ij}$ of sizes at least $\epsilon t$ and discrepancy greater than $\epsilon$. Refine each class by all its incident witness subsets. There are at most $k-1$ cuts in each class and at most $2^k$ resulting atoms. The witness rectangle is a union of refined rectangles. By the Cauchy-Schwarz inequality, its contribution to the variance identity is at leastIndeed, the sum of squared deviations on the witness rectangle is at least its total weight times the square of their weighted arithmetic mean. If more than $\epsilon k^2$ unordered pairs are irregular, summing even just one orientation of each givesprovided the exceptional set has at most $n/2$ vertices. This is the strictly positive regularity energy increment.

Restore equal class sizes without losing that increment. Divide every witness atom into blocks of size $\ell =\lfloor t/4^k\rfloor$ and make every leftover vertex an exceptional singleton. This is a further refinement of a set partition, so it cannot decrease $q$. There are at most $k{2}^k$ atoms, hence fewer than $k{2}^k\ell \le n{2}^{-k}$ newly exceptional vertices. If $t\ge 2\cdot 4^k$, then $\ell \ge t/(2\cdot 4^k)$, so the number of full blocks is at most $2k{4}^k$. Each original class produces at least one full block: its leftovers occupy less than $2^k\ell$, whereas $t\ge 4^k\ell >2^k\ell$. Thus the new class count is at least $k$.

Choose $R_{\ast }=\lceil 4{\epsilon }^{-5}\rceil +1$, and choose an initial integer $k_0\ge m_0$ large enough that $R_{\ast }{2}^{-k_0}\le \epsilon /2$. Initially partition into $k_0$ equal classes and fewer than $k_0$ exceptional vertices. Take $n_0$ large enough that this initial exception is at most $\epsilon n/2$. During at most $R_{\ast }$ rounds, the additional exception is at most $R_{\ast }n{2}^{-k_0}\le \epsilon n/2$, so it never exceeds $\epsilon n\le n/2$.

A bound on class counts is obtained by iterating $k\mapsto 2k{4}^k$ at most $R_{\ast }$ times starting at $k_0$; call the resulting bound $M$. Increasing $n_0$ further to satisfy $n_0\ge 4M{4}^M$ guarantees $t\ge n/(2k)\ge 2\cdot 4^k$ at every round, so all full-block constructions are valid. If the desired regularity had not been reached after $R_{\ast }$ refinements, the regularity energy increments would total more than one, impossible. Therefore the process terminates with the required partition and bounds. The singleton treatment of discarded vertices is what preserves regularity energy monotonicity during equalization.

First derive the triangle removal lemma from the Szemerédi regularity lemma. Given an allowed deletion fraction $0<\eta <1$, take $d=\eta /10$, $m_0=\lceil 10/\eta \rceil$, and $0<\epsilon \le \min (d/4,\eta /100,1/8)$. Apply part (i), with upper class bound $M$. Delete edges incident with $V_0$, inside each nonexceptional class, between irregular pairs, and between regular pairs of subset density less than $d$. Their total number is at mostThese four terms are bounded respectively by $\epsilon n^2$, $n^2/(2m_0)$, $\epsilon n^2$, and $d{n}^2/2$.

If a triangle in a graph remains, its three vertices lie in three distinct equal classes, all three regular pairs with subset density at least $d$. The permitted regular triangle counting lemma gives at least $(d^3/4)t^3$ triangles in a graph in the original graph, where $t$ is the class size. This lower bound can also be checked directly: all but $2\epsilon t$ vertices of the first class have at least $(d-\epsilon )t$ neighbors in each of the other two. Those neighborhoods are large enough to use the regular pair condition on the remaining pair, giving at least $(d-\epsilon {)}^3{t}^2$ edges between them. Hence the total is at least $(1-2\epsilon )(d-\epsilon {)}^3{t}^3\ge (d^3/4)t^3$.

Since $t\ge n/(2M)$, a surviving triangle in a graph forces at least $d^3{n}^3/(32M^3)$ original triangles in a graph. Thus a graph with fewer than $\xi n^3$ triangles in a graph, where $\xi =d^3/(64M^3)>0$, can be made triangle-free by deleting fewer than $\eta n^2$ edges, for all sufficiently large $n$. This proves the removal lemma needed here.

Now use the triangle-removal proof of Roth theorem. Fix a subset density lower bound $\delta >0$ and suppose $A\subseteq [N]$, $|A|\ge \delta N$, has no nonconstant three-term arithmetic progression. Set $m=2N+1$ and $G={\mathbb{Z}}_m$. Use three disjoint copies $X,Y,Z$ of $G$ and put edges according toDivision by two is valid because $m$ is odd. A triangle in a graph corresponds to $a=y-x$, $b=z-y$, $c=(z-x)/2$ with $a,b,c\in A$ and $a+b=2c$. Since $A\subseteq [N]$ and $|a+b-2c|<m$, this congruence is an integer equality. Progression-freeness therefore forces $a=b=c$.

Every triangle in a graph is consequently of the form $(x,x+a,x+2a)$ with $x\in G,a\in A$, so there are exactly $m|A|$ triangles in a graph. These triangles in a graph are edge-disjoint: an $XY$ edge determines $(x,a)$; a $YZ$ edge determines $a$ and then $x$; and an $XZ$ edge determines $a=(z-x)/2$ and $x$. Eliminating them all requires at least $m|A|$ edge deletions.

The graph has $3m$ vertices but only $m|A|\le mN=O(m^2)$ triangles in a graph. Take $\eta =\delta /100$. For large enough $N$ its triangle in a graph count is below $\xi (3m{)}^3$, so removal requires fewer than $\eta (3m{)}^2=9\delta m^2/100$ deletions. Yeta contradiction. Therefore every fixed positive-density subset of a sufficiently long interval contains a nonconstant three-term arithmetic progression.

This proves the qualitative Roth theorem on three-term arithmetic progressions. The quantitative bound from part 2(i) came from the explicit Fourier iteration; the regularity-removal argument gives a density-dependent threshold without that double-logarithmic estimate.