= Locally dense graph thinning lemma
For every $\varepsilon>0$ there are $\delta>0$ and $n_0$ such that the following holds for $n\geq n_0$ and $\delta\leq p\leq1$. If a finite <simple graph> $G$ satisfies
$$
e_G(A,B)\geq p|A||B|
$$
for all disjoint $A,B$ of sizes at least $\delta n$, it has a <spanning subgraph> $G'$ with
$$
\bigl|e_{G'}(A,B)-p|A||B|\bigr|\leq\varepsilon n^2
$$
for 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 $\varepsilon$, 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\geq 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.
Back to article page
