Graph removal lemma


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 be a graph with vertices. The graph removal lemma states that for any
, there exists a constant such that for any -vertex graph with fewer than subgraphs isomorphic to, it is possible to eliminate all copies of by removing at most edges from.
An alternative way to state this is to say that for any -vertex graph with subgraphs isomorphic to, it is possible to eliminate all copies of by removing edges from. Here, the indicates the use of little o notation.

Proof

Proof of the triangle removal lemma

The graph removal lemma was originally proven for the case that the subgraph is a triangle by Imre Z. Ruzsa and Endre Szemerédi in 1978, using the Szemerédi regularity lemma. A key element of the proof is the triangle counting lemma.
Informally, if vertex subsets of are "random-like" with pairwise edge densities, then we expect the number of triples such that form a triangle in to be
More precisely, suppose vertex subsets of are pairwise -regular, and suppose the edge densities are all at least. Then the number of triples such that form a triangle in is at least
To prove the triangle removal lemma, consider an -regular partition of the vertex set of. This exists by the Szemerédi regularity lemma. The idea is to remove all edges between irregular pairs, low-density pairs, and small parts, and prove that if at least one triangle still remains, then many triangles remain. Specifically, remove all edges between parts and if
This procedure removes at most edges. If there exists a triangle with vertices in after these edges are removed, then the triangle counting lemma tells us there are at least
triples in which form a triangle. Thus, we may take

Proof of the graph removal lemma

The triangle removal lemma was extended to general subgraphs by Erdős, Frankl, and Rödl in 1986. The proof is analogous to the proof of the triangle removal lemma, and uses a generalization of the triangle counting lemma, the graph counting lemma.

Generalizations

The graph removal lemma was later extended to directed graphs and to hypergraphs. An alternative proof, providing stronger bounds on the number of edges that need to be removed as a function of the number of copies of the subgraph, was published by Jacob Fox in 2011.
A version for induced subgraphs was proved by Alon, Fischer, Krivelevich, and Szegedy in 2000. It states that for any graph with vertices and, there exists a constant such that if an -vertex graph has fewer than induced subgraphs isomorphic to, then it is possible to eliminate all induced copies of by adding or removing fewer than edges. Note that the proof of the graph removal lemma does not easily extend to induced subgraphs because given a regular partition of the vertex set of, it now becomes unclear whether to add or remove all the edges between irregular pairs. This issue must be remedied using the strong regularity lemma.

Applications