= Irregular pair of vertex sets
= Irregular pair
{synonym}
For disjoint nonempty <vertex> <sets> $U,V$ of a <graph>, an $\varepsilon$-irregular pair is one that is not an $\varepsilon$-<regular pair of vertex sets>. Equivalently there are witnesses $U'\subseteq U$, $V'\subseteq V$ with $|U'|\geq\varepsilon|U|$, $|V'|\geq\varepsilon|V|$ and $|d(U',V')-d(U,V)|>\varepsilon$. Splitting both cells by these witnesses increases their contribution to the <regularity energy> by at least $\varepsilon^4|U||V|/n^2$: the witness rectangle has relative weight at least $\varepsilon^2$, its mean discrepancy has magnitude greater than $\varepsilon$, and the <Cauchy-Schwarz inequality> bounds the weighted sum of squared discrepancies below by the rectangle weight times its squared mean. This is the local increment in the <energy-increment proof of Szemerédi regularity>.
Back to article page
