Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 147 / 3 / ii / Solution

Give $X\times Y$ the uniform probability measure and let $f$ be the indicator function of the edge set. For partitions $\mathcal{P}=\{X_i\}$ and $\mathcal{Q}=\{Y_j\}$, define the energyBecause conditional expectation is an orthogonal projection in L2 space, $0\le \mathcal{E}\le \Vert f{\Vert }_2^2\le 1$.

Suppose the pair of partitions is not $\epsilon$-regular. For each irregular $(X_i,Y_j)$ choose witnesses $A_{ij}\subseteq X_i$ and $B_{ij}\subseteq Y_j$ withRefine each $X_i$ by all sets $A_{ij}$ and each $Y_j$ by all sets $B_{ij}$. If the old partitions have $r,s$ cells, the refined ones have at most $r{2}^s,s{2}^r$ cells.

The Pythagorean theorem for the two nested conditional-expectation projections givesInside an irregular $X_i\times Y_j$, the witness rectangle occupies at least an ${\epsilon }^2$ proportion and the mean of the displayed difference over it has magnitude greater than $\epsilon$. The Cauchy-Schwarz inequality therefore gives an energy gain greater thanfrom that pair. Since irregular pairs have total weight greater than $\epsilon$, the complete refinement raises the energy by more than ${\epsilon }^5$.

Energy is at most one, so after at most $\lceil {\epsilon }^{-5}\rceil$ refinements the process stops at an $\epsilon$-regular pair of partitions. Iterating the cell-count bounds $r\mapsto r{2}^s$ and $s\mapsto s{2}^r$ from $r=s=1$ a bounded number of times produces a finite $K(\epsilon )$ independent of $G$. This proves the Bipartite Szemerédi regularity lemma.