Equitable regularity energy ($q(\mathcal{P})$)

For a set partition $\mathcal{P}$ of the vertices of a graph of order $n$, definewhere the sum is ordered, the adjacency indicator defines the density also on diagonal pairs, and exceptional vertices are treated as singleton parts. Refinement cannot decrease this energy, by the Cauchy-Schwarz inequality. An irregular pair of equal cells of size $m$, with witnesses of relative size at least $\epsilon$ and density discrepancy greater than $\epsilon$, increases the energy by more than ${\epsilon }^4{m}^2/n^2$ for each orientation. Splitting refined atoms into equal chunks and leftover singleton parts is a further refinement, so restoring equitability causes no energy loss.

In a proof of the Szemerédi regularity lemma, suppose $k$ equal classes have size $L$ and witness splitting creates at most $2^k$ atoms per class. Divide every atom into blocks of size $\ell =\lfloor L/4^k\rfloor$, putting leftovers into the exceptional set. At most $k{2}^k\ell \le kL{2}^{-k}$ vertices are lost. When $L\ge 2\cdot 4^k$, at most $2k{4}^k$ blocks remain. For equitable regularity energy defined by omitting exceptional vertices, the loss from discarding a fraction $r$ is at most $2r$: only ordered pairs incident with discarded vertices are removed, and every squared edge density of a bipartite graph is at most one. This provides a quantitative way to restore equal class sizes after each energy increment.

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 isIt 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 $\epsilon$ and edge density of a bipartite graph discrepancy greater than $\epsilon$, its contribution, after division by the squared total vertex count, exceeds ${\epsilon }^4|U||V|/N^2$.