= Solution
For nonempty $A\subseteq X$ and $B\subseteq Y$, their <edge density of a bipartite graph> is
$$
d(A,B)=\frac{e(A,B)}{|A||B|}.
$$
The pair $(A,B)$ is $\varepsilon$-regular when every $A'\subseteq A$ and $B'\subseteq B$ with $|A'|\geq\varepsilon|A|$ and $|B'|\geq\varepsilon|B|$ satisfy
$$
|d(A',B')-d(A,B)|\leq\varepsilon.
$$
For <set partitions> $X=X_1\sqcup\cdots\sqcup X_r$ and $Y=Y_1\sqcup\cdots\sqcup Y_s$, the <regular pair of bipartite partitions> condition is
$$
\boxed{\sum_{(i,j):\,(X_i,Y_j)\text{ is not }\varepsilon\text{-regular}}|X_i||Y_j|
\leq\varepsilon|X||Y|.}
$$
Back to article page
