Graph removal lemma
[2] The graph removal lemma can be used to prove Roth's theorem on 3-term arithmetic progressions,[3] and a generalization of it, the hypergraph removal lemma, can be used to prove Szemerédi's theorem.
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
[6] 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.
[7] The modern formulation of the graph removal lemma was first stated by Füredi in 1994.
A key component of the proof of the graph removal lemma is the graph counting lemma about counting subgraphs in systems of regular pairs.
should behave like a random Erdős–Rényi-like graph, where every pair of vertices
The following claim appears in the literature under name of the blow-up lemma and was first proven by Komlós, Sárközy, and Szemerédi.
[9] The precise statement here is a slightly simplified version due to Komlós, who referred to it also as the key lemma, as it is used in numerous regularity-based proofs.
We will provide a proof of the counting lemma in the case when
To prove the triangle removal lemma, consider an
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.
after these edges are removed, then the triangle counting lemma tells us there are at least
A natural generalization of the graph removal lemma is to consider induced subgraphs.
In property testing, it is often useful to consider how far a graph is from being induced H-free.
A version of the graph removal lemma for induced subgraphs was proved by Alon, Fischer, Krivelevich, and Szegedy in 2000.
vertices where non-edges are blue and edges are red), and a constant
Notice that our previous "cleaning" process, where we remove all edges between irregular pairs, low-density pairs, and small parts, only involves removing edges.
However, there are situations in the induced case where the optimal edit distance involves changing edge colors from blue to red as well.
where the following properties are satisfied: The main idea of the proof of this corollary is to start with two partitions
This allows us to consider edges and non-edges when we perform our cleaning argument.
With these results, we are able to prove the induced graph removal lemma.
which satisfy the conditions of the Corollary of the Strong Regularity Lemma.
[12] We then can perform a "cleaning" process where we remove all edges between pairs of parts
with low density, and we can add all edges between pairs of parts
to be extremely small, bounded by a tower function whose height is polynomial in
This proof can be also rephrased using the Frieze-Kannan weak regularity lemma as noted by Conlon and Fox.
is necessary for the graph removal lemma to hold, while for bipartite
Indeed, as the triangle removal lemma implies Roth's theorem, existence of large Salem-Spencer sets may be translated to an upper bound for
