Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 4 / a / Solution

For disjoint nonempty vertex sets $A,B$, writeThe pair $(A,B)$ is $\epsilon$-uniform ifwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \epsilon |A|$, and $|Y|\ge \epsilon |B|$.

The Szemerédi regularity lemma states that for every $\epsilon >0$ and integer $m_0$ there are $M,n_0$ such that every graph on $n\ge n_0$ vertices has a partitionwith $m_0\le m\le M$, $|V_0|\le \epsilon n$, equal sizes $|V_1|=\cdots =|V_m|$, and at most $\epsilon m^2$ pairs $(V_i,V_j)$ that are not $\epsilon$-uniform.