Minimum degree and the graph removal lemma

The clique removal lemma says that for everyr ≥ 3$r\ge 3$ andε > 0$\varepsilon \gt 0$ , there exists someδ > 0$\delta \gt 0$ so that everyn$n$ ‐vertex graphG$G$ with fewer thanδ n r$\delta {n}^{r}$ copies ofK r${K}_{r}$ can be madeK r${K}_{r}$ ‐free by removing at mostε n 2$\varepsilon {n}^{2}$ edges. The dependence ofδ$\delta $ onε$\varepsilon $ in this result is notoriously difficult to determine: it is known thatδ − 1${\delta }^{-1}$ must be at least super‐polynomial inε − 1${\varepsilon }^{-1}$ , and that it is at most of tower type inlog   ε − 1$\mathrm{log} {\varepsilon }^{-1}$ . We prove that if one imposes an appropriate minimum degree condition onG$G$ , then one can actually takeδ$\delta $ to be a linear function ofε$\varepsilon $ in the clique removal lemma. Moreover, we determine the threshold for such a minimum degree requirement, showing that above this threshold we have linear bounds, whereas below the threshold the bounds are once again super‐polynomial, as in the unrestricted removal lemma. We also investigate this question for other graphs besides cliques, and prove some general results about how minimum degree conditions affect the bounds in the graph removal lemma.