= Solution
For disjoint nonempty vertex sets $A,B$, write
$$
d(A,B)=\frac{e(A,B)}{|A||B|}.
$$
The pair $(A,B)$ is <regular pair of vertex sets>[$\varepsilon$-uniform] if
$$
|d(X,Y)-d(A,B)|\leq\varepsilon
$$
whenever $X\subseteq A$, $Y\subseteq B$, $|X|\geq\varepsilon|A|$, and $|Y|\geq\varepsilon|B|$.
The <Szemerédi regularity lemma> states that for every $\varepsilon>0$ and integer $m_0$ there are $M,n_0$ such that every graph on $n\geq n_0$ vertices has a partition
$$
V=V_0\sqcup V_1\sqcup\cdots\sqcup V_m
$$
with $m_0\leq m\leq M$, $|V_0|\leq\varepsilon n$, equal sizes $|V_1|=\cdots=|V_m|$, and at most $\varepsilon m^2$ pairs $(V_i,V_j)$ that are not $\varepsilon$-uniform.
Back to article page
