= Solution
For disjoint nonempty vertex sets $A,B$, write
$$
d(A,B)=\frac{e(A,B)}{|A||B|}.
$$
The pair $(A,B)$ is a <regular pair of vertex sets> with parameter $\epsilon$ if
$$
|d(X,Y)-d(A,B)|\le\epsilon
$$
whenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge\epsilon|A|$, and $|Y|\ge\epsilon|B|$.
The <Szemerédi regularity lemma> says that for every $\epsilon>0$ and $m_0$ there are $M,n_0$ such that every graph on at least $n_0$ vertices has a partition
$$
V=V_0\sqcup V_1\sqcup\cdots\sqcup V_m,
$$
where $m_0\le m\le M$, $|V_0|\le\epsilon|V|$, the classes $V_1,\ldots,V_m$ have equal size, and all but at most $\epsilon m^2$ pairs $(V_i,V_j)$ are $\epsilon$-uniform.
Back to article page
