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 formula_1 be a  graph with formula_2 vertices. The graph removal lemma states that for any formula_3, there exists a constant formula_4 such that for any formula_5-vertex graph formula_6 with fewer than formula_7 subgraphs isomorphic to formula_1, it is possible to eliminate all copies of formula_1 by removing at most formula_10 edges from formula_6. An alternative way to state this is to say that for any formula_5-vertex graph formula_6 with formula_14 subgraphs isomorphic to formula_1, it is possible to eliminate all copies of formula_1 by removing formula_17 edges from formula_6. Here, the formula_19 indicates the use of little o notation. In the  case when formula_1 is a triangle, resulting lemma is called triangle removal lemma. History. The original motivation for the study of triangle removal lemma was Ruzsa–Szemerédi problem. 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 formula_5 vertices contains formula_17 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 Ruzsa–Szemerédi problem to arbitrary formula_23-uniform graphs, Erdős, Frankl, and Rödl provided statement for general graphs very close to the modern graph removal lemma: if graph formula_24 is a homomorphic image of formula_24, then any formula_26-free graph formula_6 on formula_5 vertices can be made formula_24-free by removing formula_17 edges. The modern formulation of 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 utilizing Szemerédi regularity lemma. Graph counting lemma. A key component of the proof of  graph removal lemma is the graph counting lemma about counting subgraphs in systems of regular pairs. Graph counting lemma is also very useful on its own. According to Füredi, it is used "in most applications of regularity lemma". Heuristic argument. Let formula_1 be a graph on formula_2 vertices, whose vertex set is formula_33 and edge set is formula_34. Let formula_35 be sets of vertices of some graph formula_6 such that for all formula_37 pair formula_38 is formula_39-regular (in the sense of regularity lemma). Let also formula_40 be the density between sets formula_41 and formula_42. Intuitively, regular pair formula_43 with  density formula_44 should behave like a random Erdős–Rényi-like graph, where every pair of vertices formula_45 is selected to be an edge independently with probability formula_44. This suggests that the number of copies of formula_1 on vertices formula_48 such that formula_49 should be close to the expected number from Erdős–Rényi model: formula_50 where formula_51 and formula_52 are the edge set and the vertex set of formula_1. Precise statement. The straightforward formalization of above heuristic claim is as follows. Let formula_1 be a graph on formula_2 vertices, whose vertex set is formula_33 and edge set is formula_34. Let formula_58  be arbitrary. Then there exists formula_59 such that for any formula_35 as above, satisfying formula_61 for all formula_37, the number of graph homomorphisms from formula_1 to formula_6 such that vertex formula_65 is mapped to formula_41 is not smaller then formula_67 Blow-up Lemma. One can even find bounded degree subgraphs of blow-ups of formula_1 in a similar setting. 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. 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. Let formula_26 be an arbitrary graph and formula_70. Construct formula_71 by replacing each vertex formula_72 of formula_1 by independent set formula_74 of size formula_75 and replacing every edge formula_76 of formula_1 by complete bipartite graph on formula_78. Let formula_79 be arbitrary reals, formula_80 be a potiive integer and let formula_24 be a subgraph of formula_71 with formula_2 vertices and with maximum degree formula_84. Define formula_85. Finally, let formula_6 be a graph and formula_35 be disjoint sets of vertices of formula_6 such that whenever formula_89 then formula_38 is a formula_39 -regular pair with density at least formula_92. Then if formula_93 and formula_94, the number of injective graph homomorphisms from formula_24 to formula_6 is at least formula_97. In fact, one can only restrict to counting homomorphisms such that any vertex formula_98 of formula_24 such that formula_100 is mapped to a vertex in formula_41. Proof. We will provide proof of the counting lemma in the case when formula_1 is a triangle (triangle counting lemma). The proof of the general case, as well as the proof of the blow-up lemma, are very similar and do not require different techniques. Take formula_103. Let  formula_104 be the set of those vertices in formula_105 which have at least formula_106 neighbors in formula_107 and at least formula_108 neighbors in formula_109. Note that if there were more than formula_110 vertices in formula_105 with less than formula_106 neighbors in formula_107, then these vertices together with whole formula_107 would witness formula_39-irregularity of the pair formula_116. Repeating this argument for formula_109 shows that we must have formula_118. Now take arbitrary formula_119 and define formula_120 and formula_121 as neighbors of formula_122 in formula_107 and formula_109 respectively. By definition formula_125 and formula_126 so by regularity of formula_127 we obtain existence of  at least formula_128 triangles containing formula_122. Since formula_122 was chosen arbitrarily from the set formula_131 of size at least formula_132, we obtain a total of at least formula_133 which finishes the proof as formula_103. Proof. Proof of the triangle removal lemma. To prove the triangle removal lemma, consider an formula_135-regular partition formula_136 of the vertex set of formula_6. 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 formula_74 and formula_139 if This procedure removes at most formula_10 edges. If there exists a triangle with vertices in formula_141 after these edges are removed, then the triangle counting lemma tells us there are at least formula_142 triples in formula_143 which form a triangle. Thus, we may take formula_144 Proof of the graph removal lemma. The proof of the case of general formula_1 is analogous to the triangle case, and uses graph counting lemma instead of triangle counting lemma. Induced Graph Removal Lemma. 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 graph formula_6 is considered to contain an induced subgraph formula_1 if there is an injective map formula_148 such that formula_149 is an edge of formula_6 if and only if formula_151 is an edge of formula_1. Notice that non-edges are considered as well. formula_6 is induced formula_1-free if there is no induced subgraph formula_6. We define formula_6 as formula_39-far from being induced formula_1-free if we cannot add or delete formula_10 edges to make formula_6 induced formula_1-free. Formulation . A version of the Graph Removal for induced subgraphs was proved by Alon, Fischer, Krivelevich, and Szegedy in 2000. It states that for any graph formula_1 with formula_2 vertices and formula_3, there exists a constant formula_165 such that if an formula_5-vertex graph formula_6 has fewer than formula_7 induced subgraphs isomorphic to formula_1, then it is possible to eliminate all induced copies of formula_1 by adding or removing fewer than formula_10 edges. The problem can be reformulated as follows: Given a red-blue coloring formula_172 of the complete graph formula_173 (Analogous to the graph formula_1 on the same formula_2 vertices  where non-edges are blue, edges are red), and a constant formula_3, then there exists a constant formula_165 such that for any red-blue colorings of formula_178 has fewer than formula_7 subgraphs isomorphic to formula_172, then it is possible to eliminate all copies of formula_1 by changing the colors of fewer than formula_10 edges. Notice that our previous "cleaning" process, where we remove all edges between irregular pairs, low-density pairs, and small parts, only involves removing edges. Removing edges only corresponds to changing edge colors from red to blue. However, there are situations in the induced case where the  optimal edit distance involves changing edge colors from blue to red as well. Thus, the Regularity Lemma is insufficient to prove Induced Graph Removal Lemma. The proof of the Induced Graph Removal Lemma must take advantage of the strong regularity lemma. Proof. Strong Regularity Lemma. The strong regularity lemma is a strengthened version of Szemerédi's Regularity Lemma. For any infinite sequence of constants formula_183, there exists an integer formula_184 such that for any graph formula_6, we can obtain two (equitable) partitions formula_186 and formula_187 such that the following properties are satisfied: The function formula_198 is defined to be the  energy function defined in Szemerédi regularity lemma. Essentially, we can find a pair of partitions formula_199 where formula_187 is regular compared to formula_186, and at the same time formula_199 are close to each other. (This property is captured in the third condition) Corollary of the Strong Regularity Lemma. The following corollary of the strong regularity lemma is used in the proof of the Induced Graph Removal Lemma. For any infinite sequence of constants formula_183, there exists formula_58 such that there exists a partition formula_205 and subsets formula_206 for each formula_72 where the following properties are satisfied: The main idea of  the proof of this corollary is to start with two partitions formula_186 and formula_187 that satisfy the Strong Regularity Lemma where formula_217. Then for each part formula_218, we uniformly at random choose some part formula_219 that is a part in formula_187. The expected number of irregular pairs formula_209 is less than 1. Thus, there exists some collection of formula_222 such that every pair is formula_195-regular! The important aspect of this corollary is that pair of formula_224 are formula_195-regular! This allows us to consider edges and non-edges when we perform our cleaning argument. Proof of Sketch of the  Induced Graph Removal Lemma. With these results, we are able to prove the Induced Graph Removal Lemma. Take any graph formula_6 with formula_5 vertices that has less than formula_228 copies of formula_1. The idea is to start with a collection of vertex sets formula_222 which satisfy the conditions of the Corollary of the Strong Regularity Lemma. We then can perform a "cleaning" process where we remove all edges between pairs of parts formula_209 with low density, and we can add all edges between pairs of parts formula_209 with high density. We choose the density requirements such that we added/deleted  at most formula_10 edges. If the new graph has no copies of formula_1, then we are done. Suppose the new graph has a copy of formula_1. Suppose the vertex formula_236 is embedded in formula_237. Then if there is an edge connecting formula_238 in formula_1, then formula_224 does not have low density. (Edges between formula_224 were not removed in the cleaning process) Similarly, if there is not an edge connecting formula_238 in formula_1, then formula_224 does not have high density. (Edges between formula_224 were not added in the cleaning process) Thus, by a similar counting argument to the proof of the  triangle counting lemma, that is the graph counting lemma, we can show that formula_6 has more than formula_228 copies of formula_1. Generalizations. The graph removal lemma was later extended to directed graphs and to hypergraphs. Quantitative bounds. Usage of regularity lemma in the proof of graph removal lemma forces formula_249 to be extremely small, bounded by tower function of hight polynomial in formula_250 that is formula_251 (here formula_252 is the tower of twos of height formula_253). Tower function of height formula_254 is necessary in all regularity proofs as is implied by results of Gowers on lower bounds in regularity lemma . However, in 2011 Fox provided a new proof of graph removal lemma which does not use regularity lemma, improving the bound to formula_255 (here formula_2 is number of vertices of removed graph formula_1). His proof, however, uses regularity-related ideas such as energy increment, but with different notion of energy, related to entropy. This proof can be also rephrased using Frieze-Kannan weak regularity lemma as noted by Conlon and Fox. In the special case of bipartite formula_1 it was shown that formula_259 is sufficient. There is a large gap between upper and lower bounds for formula_249 in the general  case. The current best result true for all graphs formula_1 is due to Alon and states that for each nonbipartite formula_1 there exists constant formula_263 such that formula_264 is necessary for the graph removal lemma to hold while for bipartite formula_1 the optimal formula_249 has polynomial dependence on formula_39, which matches the lower bound. Construction for nonbipartite case is a consequence of Behrend construction of large Salem-Spencer set. Indeed, as triangle removal lemma implies Roth's theorem, existence of large Salem-Spencer set may be translated to an upper bound for formula_249 in the triangle removal lemma. This method  can be leveraged for arbitrary nonbipartite formula_1 to give aforementioned bound. Applications. Graph theory. </math> where formula_270 is the Turán density of formula_1.