 Induced-edge discrepancy criterion for regular vertex pairs

Let $0<ϵ<1$ and suppose an $N$-vertex graph has induced-edge discrepancies $|e(G[W])-p(\genfrac{}{}{0ex}{}{|W|}{2})|<{ϵ}^5{N}^2/9$ whenever $|W|\ge {ϵ}^{2}N$. Any two disjoint vertex sets of size at least $ϵN$ then form an epsilon-regular pair. Indeed, inclusion-exclusion of the induced edge counts giveswhenever both sets have size at least ${ϵ}^{2}N$. The original pair has density within ${ϵ}^3/3$ of $p$, while each pair of allowed relative subsets has density within $ϵ/3$ of $p$. Their densities differ by less than $(ϵ+{ϵ}^3)/3<ϵ$.

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/ϵ$ once $N$ is sufficiently large to absorb integer rounding. That size condition cannot be discarded if all $k$ nonexceptional classes must be nonempty.