= Locally dense graph thinning lemma
For every $\varepsilon>0$ there is $\delta>0$ such that a graph satisfying $e(A,B)\geq p|A||B|$ whenever $|A|,|B|\geq\delta n$, with $p\geq\delta$, has a spanning subgraph $G'$ satisfying
$$
|e_{G'}(A,B)-p|A||B||\leq\varepsilon n^2
$$
for all disjoint $A,B$. Partition into a fixed large number of nearly equal parts, independently thin each cross-pair to expected density $p$, and apply a concentration inequality and a union bound over all pairs $A,B$.
Back to article page
