Graph removal lemma for a fixed ordinary subgraph

We prove the contrapositive. Put $h=\mathrm{\mid }V(H)\mathrm{\mid }$, choose $0<\eta <1$ with $\eta \ll ϵ$, then choose a regularity parameter $0<\gamma <\eta$ small enough for [L2], so $0<\gamma <1$ as [L1] requires. Set $m_0=\lceil 8\mathrm{/}ϵ\rceil$ and require $n_0\ge \max (M(\gamma ,m_0),8\mathrm{/}ϵ)$. Apply [L1] at $\gamma$ with minimum part count $m_0$, obtaining an equitable $\gamma$-regular partition into $k$ parts with $m_0\le k\le M$.

From $G$ delete every edge inside a partition part, every edge across a $\gamma$-irregular pair, and every edge across a regular pair of density below $\eta$. Call the resulting graph $G^{\mathrm{\prime }}$.

Equitability bounds the within-part deletions by ${\sum }_i\mathrm{\mid }{V}_i{\mathrm{\mid }}^2\le n{\max }_i\mathrm{\mid }{V}_i\mathrm{\mid }\le n(n\mathrm{/}k+1)=n^2\mathrm{/}k+n$, and $k\ge m_0\ge 8\mathrm{/}ϵ$ together with $n\ge n_0\ge 8\mathrm{/}ϵ$ make this at most $ϵn^2\mathrm{/}4$ by [L1]; $\gamma$-regularity bounds the irregular-pair deletions by $\gamma n^2$; and the low-density pairs contribute at most $\eta n^2$. Choose $\gamma ,\eta$ so that $\gamma +\eta <ϵ\mathrm{/}2$. Hence fewer than $ϵn^2$ edges were deleted, each changing one unordered vertex pair by [L3].

Assume that fewer than $ϵn^2$ deletions cannot make $G$ $H$-free. Then $G^{\mathrm{\prime }}$ contains a copy of $H$. Assign to each vertex of $H$ the partition part containing its image. Every edge of $H$ lies across a $\gamma$-regular pair of density at least $\eta$.

Apply [L2] to those assigned parts. Since each has size at least $n\mathrm{/}(2M)$ for the fixed regularity bound $M$, the original graph contains at least $c{\prod }_{i=1}^h\mathrm{\mid }{W}_i\mathrm{\mid }\ge c(2M{)}^{-h}{n}^h$ injective copies of $H$. Put $\delta =c(2M{)}^{-h}$.

Thus every graph requiring at least $ϵn^2$ edge deletions contains at least $\delta n^h$ copies of $H$, which is the contrapositive of the Statement.