Weighted Szemerédi regularity lemma (${\sum }_{(i,j)\text{ irregular}}|V_i||V_j|\le \epsilon n^2$)

For every $\epsilon >0$, all sufficiently large finite graphs admit a set partition into at most $M(\epsilon )$ nonempty cells, each of size at most $\epsilon n$, with the displayed ordered irregular-pair weight bound. Start with small cells. Use regularity energy including diagonal rectangles, refine simultaneously by the witness subsets of all irregular pairs, and apply the refinement variance identity for regularity energy. Each failing round raises energy by more than ${\epsilon }^5$, while energy lies in $[0,1]$. The recurrence $k\mapsto k{2}^k$ bounds the final cell count. Equitability is unnecessary for this weighted version.

A partition with at most $M$ cells has at most $\epsilon n$ vertices in cells smaller than $\epsilon n/M$. Deleting all edges incident to those vertices costs at most $\epsilon n^2$ edges. Every remaining cell has a fixed positive fraction of all vertices, which permits a regular triangle counting lemma to give a cubic count without requiring equal cell sizes.