= Small-cell deletion in weighted regularity
{title2=$|V_i|<\varepsilon n/M\Longrightarrow\text{at most }\varepsilon n\text{ deleted vertices}$}
A partition with at most $M$ cells has at most $\varepsilon n$ vertices in cells smaller than $\varepsilon n/M$. Deleting all edges incident to those vertices costs at most $\varepsilon 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.
Back to article page
