Regular pair of bipartite partitions
= Regular pair of bipartite partitions
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$.