= Solution
For disjoint nonempty vertex sets $X,Y$, their <edge density of a bipartite graph> is
$$
d(X,Y)=\frac{e(X,Y)}{|X||Y|}.
$$
The pair $(X,Y)$ is a <regular pair of vertex sets>[$\varepsilon$-regular pair] if
$$
|d(X',Y')-d(X,Y)|\leq\varepsilon
$$
whenever $X'\subseteq X$, $Y'\subseteq Y$, $|X'|\geq\varepsilon|X|$, and $|Y'|\geq\varepsilon|Y|$. A partition $V_0,V_1,\ldots,V_m$ is equitable when $|V_1|=\cdots=|V_m|$; $V_0$ is its exceptional class.
The <Szemerédi regularity lemma> says that for every $\varepsilon>0$ and $m_0$ there are integers $M,n_0$ such that every graph on at least $n_0$ vertices has an equitable partition
$$
V=V_0\sqcup V_1\sqcup\cdots\sqcup V_m
$$
with
$$
m_0\leq m\leq M,
\qquad |V_0|\leq\varepsilon|V|,
$$
for which all but at most $\varepsilon m^2$ pairs $(V_i,V_j)$, $1\leq i<j\leq m$, are $\varepsilon$-regular.
Back to article page
