Locally dense graph thinning lemma

For every $\epsilon >0$ there are $\delta >0$ and $n_0$ such that the following holds for $n\ge n_0$ and $\delta \le p\le 1$. If a finite simple graph $G$ satisfiesfor all disjoint $A,B$ of sizes at least $\delta n$, it has a spanning subgraph $G^{\prime }$ withfor all disjoint $A,B$. This turns local lower density into an approximately uniform cut density by deleting edges.

Use the Szemerédi regularity lemma with regularity parameter $\eta$ much smaller than $\epsilon$, and with a sufficiently large lower bound on the number of cells. If the number of cells is at most $M$, choose $\delta$ small enough that every nonexceptional cell has size at least $\delta n$. Each regular cross-pair then has density $d\ge p$. Keep each of its edges independently with probability $p/d$, and delete edges in irregular pairs, within cells and incident with the exceptional set.

On a regular pair, every sufficiently large subrectangle has density within $\eta$ of $d$; on a smaller subrectangle its area is already small. Consequently the expected discrepancy on arbitrary cuts is $O(\eta n^2)$, plus the small deleted-cell and irregular-pair budgets. A concentration inequality bounds deviations of each cut from its expectation by $o(n^2)$ with probability exponentially close to one on the $n^2$ scale. A union bound over at most $3^n$ disjoint ordered pairs of vertex subsets then supplies a simultaneous choice. Both the regular partition and the sufficiently-large-$n$ hypothesis are necessary parts of this proof; an arbitrary partition does not control subrectangles.