The Minimum Degree Removal Lemma Thresholds

Abstract

The graph removal lemma is a fundamental result in extremal graph theory which says that for every fixed graph $H$ and $\epsilon >0$, if an $n$-vertex graph $G$ contains $\epsilon n^2$ edge-disjoint copies of $H$ then $G$ contains $\hat{I}´n^{v(H)}$ copies of $H$ for some $\hat{I}´=\hat{I}´(\epsilon ,H)>0$. The current proofs of the removal lemma give only very weak bounds on $\hat{I}´(\epsilon ,H)$, and it is also known that $\hat{I}´(\epsilon ,H)$ is not polynomial in $\epsilon$ unless $H$ is bipartite. Recently, Fox and Wigderson initiated the study of minimum degree conditions guaranteeing that $\hat{I}´(\epsilon ,H)$ depends polynomially or linearly on $\epsilon$. In this paper we answer several questions of Fox and Wigderson on this topic.