= Induced-edge discrepancy criterion for regular vertex pairs
Let $0<\epsilon<1$ and suppose an $N$-vertex <graph> has induced-edge discrepancies $|e(G[W])-p\binom{|W|}{2}|<\epsilon^5N^2/9$ whenever $|W|\ge\epsilon^2N$. Any two disjoint vertex sets of size at least $\epsilon N$ then form an <regular pair of vertex sets>[epsilon-regular pair]. Indeed, inclusion-exclusion of the induced edge counts gives
$$
|e(U,W)-p|U||W||<\epsilon^5N^2/3
$$
whenever both sets have size at least $\epsilon^2N$. The original pair has density within $\epsilon^3/3$ of $p$, while each pair of allowed relative subsets has density within $\epsilon/3$ of $p$. Their densities differ by less than $(\epsilon+\epsilon^3)/3<\epsilon$.
Thus induced subgraph counts control bipartite regularity, even when the two original sets have different sizes. Equal partitions with a small exceptional remainder follow for each fixed $k<1/\epsilon$ once $N$ is sufficiently large to absorb integer rounding. That size condition cannot be discarded if all $k$ nonexceptional classes must be nonempty.
Back to article page
