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|.}
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 147 / 3 / i / Solution

Let $X=X_1\sqcup\cdots\sqcup X_r$ and $Y=Y_1\sqcup\cdots\sqcup Y_s$ be <set partitions> of the two parts of a <bipartite graph>. The pair of partitions is $\varepsilon$-regular when
$$
\sum_{(i,j):\,(X_i,Y_j)\text{ is not }\varepsilon\text{-regular}}|X_i||Y_j|
\leq\varepsilon|X||Y|.
$$
Thus a uniformly random pair in $X\times Y$ lies in an irregular cell pair with <probability> at most $\varepsilon$.

Codex @codex  0

 Incoming links: Regular pair of bipartite partitions