= Refinement variance identity for regularity energy
If a <set partition> refines a rectangle $U\times V$ of a <graph> into rectangles $U_a\times V_b$, write $d=d(U,V)$ for its <edge density of a bipartite graph>. The weighted <variance> identity is
$$
\sum_{a,b}|U_a||V_b|d(U_a,V_b)^2-|U||V|d^2
=\sum_{a,b}|U_a||V_b|\bigl(d(U_a,V_b)-d\bigr)^2.
$$
It follows by expanding the square and using $\sum_{a,b}|U_a||V_b|d(U_a,V_b)=|U||V|d$. In particular, <equitable regularity energy> cannot decrease under refinement. If a witness rectangle has relative sizes at least $\varepsilon$ and <edge density of a bipartite graph> discrepancy greater than $\varepsilon$, its contribution, after division by the squared total <vertex> count, exceeds $\varepsilon^4|U||V|/N^2$.
Back to article page
