Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 4 / a / Solution

For disjoint nonempty vertex sets $A,B$, writeThe pair $(A,B)$ is a regular pair of vertex sets with parameter $ϵ$ ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge ϵ|A|$, and $|Y|\ge ϵ|B|$.

The Szemerédi regularity lemma says that for every $ϵ>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 ϵ|V|$, the classes $V_1,\dots ,V_m$ have equal size, and all but at most $ϵm^2$ pairs $(V_i,V_j)$ are $ϵ$-uniform.