In graph theory, the graph removal lemma states that when a graph contains few copies of a given subgraph, then all of the copies can be eliminated by removing a small number of edges. The special case in which the subgraph is a triangle is known as the triangle removal lemma. The graph removal lemma can be used to prove Roth's theorem on 3-term arithmetic progressions, and a generalization of it, the hypergraph removal lemma, can be used to prove Szemerédi's theorem. It also has applications to property testing.
Formulation Let H {\displaystyle H} be a graph with h {\displaystyle h} vertices. The graph removal lemma states that for any ϵ > 0 {\displaystyle \epsilon >0} , there exists a constant δ = δ ( ϵ , H ) > 0 {\displaystyle \delta =\delta (\epsilon ,H)>0} such that for any n {\displaystyle n} -vertex graph G {\displaystyle G} with fewer than δ n h {\displaystyle \delta n^{h}} subgraphs isomorphic to H {\displaystyle H} , it is possible to eliminate all copies of H {\displaystyle H} by removing at most ϵ n 2 {\displaystyle \epsilon n^{2}} edges from G {\displaystyle G} . An alternative way to state this is to say that for any n {\displaystyle n} -vertex graph G {\displaystyle G} with o ( n h ) {\displaystyle o(n^{h})} subgraphs isomorphic to H {\displaystyle H} , it is possible to eliminate all copies of H {\displaystyle H} by removing o ( n 2 ) {\displaystyle o(n^{2})} edges from G {\displaystyle G} . Here, the o {\displaystyle o} indicates the use of little o notation. In the case when H {\displaystyle H} is a triangle, the resulting lemma is called the triangle removal lemma.
History The original motivation for the study of triangle removal lemma was the Ruzsa–Szemerédi problem. Its initial formulation due to Imre Z. Ruzsa and Szemerédi from 1978 was slightly weaker than the triangle removal lemma used nowadays and can be roughly stated as follows: every locally linear graph on n {\displaystyle n} vertices contains o ( n 2 ) {\displaystyle o(n^{2})} edges. This statement can be quickly deduced from a modern triangle removal lemma. Ruzsa and Szemerédi provided also an alternative proof of Roth's theorem on arithmetic progressions as a simple corollary. In 1986, during their work on generalizations of the Ruzsa–Szemerédi problem to arbitrary r {\displaystyle r} -uniform graphs, Erdős, Frankl, and Rödl provided a statement for general graphs very close to the modern graph removal lemma: if graph H 2 {\displaystyle H_{2}} is a homomorphic image of H 2 {\displaystyle H_{2}} , then any H 1 {\displaystyle H_{1}} -free graph G {\displaystyle G} on n {\displaystyle n} vertices can be made H 2 {\displaystyle H_{2}} -free by removing o ( n 2 ) {\displaystyle o(n^{2})} edges. The modern formulation of the graph removal lemma was first stated by Füredi in 1994. The proof generalized earlier approaches by Ruzsa and Szemerédi and Erdős, Frankl, and Rödl, also using the Szemerédi regularity lemma.
Graph counting lemma A key component of the proof of the graph removal lemma is the graph counting lemma about counting subgraphs in systems of regular pairs. The graph counting lemma is also very useful on its own. According to Füredi, it is used "in most applications of regularity lemma".
… excerpt ends here. Continue reading the full article.
