= Solution
For disjoint nonempty <sets> $X,Y$, let $e(X,Y)$ count <edges> between them. Their <edge> density is
$$
\boxed{d(X,Y)=\frac{e(X,Y)}{|X||Y|}.}
$$
The pair is $\varepsilon$-regular if every $A\subseteq X$ and $B\subseteq Y$ with $|A|\geq\varepsilon|X|$, $|B|\geq\varepsilon|Y|$ satisfies $|d(A,B)-d(X,Y)|\leq\varepsilon$.
An $\varepsilon$-regular partition has disjoint classes $V_0,V_1,\ldots,V_k$ covering $V(G)$, with $|V_0|\leq\varepsilon|V(G)|$, equal positive sizes $|V_1|=\cdots=|V_k|$, and at most $\varepsilon k^2$ unordered pairs $(V_i,V_j)$ with $1\leq i<j\leq k$ that are not $\varepsilon$-regular. The <set> $V_0$ is exceptional and its pairs need not satisfy regularity.
<Szemerédi regularity lemma> states that for every $\varepsilon>0$ and <integer> $m_0\geq1$, there are <integers> $M,n_0$ such that every <graph> with $n\geq n_0$ <vertices> has such a partition with
$$
\boxed{m_0\leq k\leq M.}
$$
The bounds depend on $\varepsilon,m_0$, not on the <graph> order. Using a strict regularity <inequality> or a slightly different <constant> in the allowed pair count gives an equivalent conventional version; the displayed convention will be used below.
Back to article page
