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.[1] The special case in which the subgraph is a triangle is known as the triangle 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.[4] It also has applications to property testing.[5]

Formulation

Let ${\displaystyle H}$ be a graph with ${\displaystyle h}$ vertices. The graph removal lemma states that for any ${\displaystyle \epsilon >0}$, there exists a constant ${\displaystyle \delta =\delta (\epsilon ,H)>0}$ such that for any ${\displaystyle n}$-vertex graph ${\displaystyle G}$ with fewer than ${\displaystyle \delta n^{h}}$ subgraphs isomorphic to ${\displaystyle H}$, it is possible to eliminate all copies of ${\displaystyle H}$ by removing at most ${\displaystyle \epsilon n^{2}}$ edges from ${\displaystyle G}$.[1]

An alternative way to state this is to say that for any ${\displaystyle n}$-vertex graph ${\displaystyle G}$ with ${\displaystyle o(n^{h})}$ subgraphs isomorphic to ${\displaystyle H}$, it is possible to eliminate all copies of ${\displaystyle H}$ by removing ${\displaystyle o(n^{2})}$ edges from ${\displaystyle G}$. Here, the ${\displaystyle o}$ 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.[6] A key element of the proof is the triangle counting lemma.

Informally, if vertex subsets ${\displaystyle X,Y,Z}$ of ${\displaystyle G}$ are "random-like" with pairwise edge densities ${\displaystyle d_{XY},d_{XZ},d_{YZ}}$, then we expect the number of triples ${\displaystyle (x,y,z)\in X\times Y\times Z}$ such that ${\displaystyle x,y,z}$ form a triangle in ${\displaystyle G}$ to be

$${\displaystyle d_{XY}d_{XZ}d_{YZ}\cdot |X||Y||Z|.}$$

More precisely, suppose vertex subsets ${\displaystyle X,Y,Z}$ of ${\displaystyle G}$ are pairwise ${\displaystyle \epsilon }$-regular, and suppose the edge densities ${\displaystyle d_{XY},d_{XZ},d_{YZ}}$ are all at least ${\displaystyle 2\epsilon }$. Then the number of triples ${\displaystyle (x,y,z)\in X\times Y\times Z}$ such that ${\displaystyle x,y,z}$ form a triangle in ${\displaystyle G}$ is at least

$${\displaystyle (1-2\epsilon )(d_{XY}-\epsilon )(d_{XZ}-\epsilon )(d_{YZ}-\epsilon )\cdot |X||Y||Z|.}$$

To prove the triangle removal lemma, consider an ${\displaystyle \epsilon /4}$-regular partition ${\displaystyle V_{1}\cup \cdots \cup V_{M}}$ of the vertex set of ${\displaystyle G}$. 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 ${\displaystyle V_{i}}$ and ${\displaystyle V_{j}}$ if

• ${\displaystyle (V_{i},V_{j})}$ is not ${\displaystyle \epsilon /4}$-regular
• the density ${\displaystyle d(V_{i},V_{j})}$ is less than ${\displaystyle \epsilon /2}$, or
• either ${\displaystyle V_{i}}$ or ${\displaystyle V_{j}}$ has at most ${\displaystyle (\epsilon /4M)n}$ vertices.

This procedure removes at most ${\displaystyle \epsilon n^{2}}$ edges. If there exists a triangle with vertices in ${\displaystyle V_{i},V_{j},V_{k}}$ after these edges are removed, then the triangle counting lemma tells us there are at least

$${\displaystyle \left(1-{\frac {\epsilon }{2}}\right)\left({\frac {\epsilon }{4}}\right)^{3}\left({\frac {\epsilon }{4M}}\right)^{3}\cdot n^{3}}$$

triples in ${\displaystyle V_{i}\times V_{j}\times V_{k}}$ which form a triangle. Thus, we may take

$${\displaystyle \delta <{\frac {1}{6}}\left(1-{\frac {\epsilon }{2}}\right)\left({\frac {\epsilon }{4}}\right)^{3}\left({\frac {\epsilon }{4M}}\right)^{3}.}$$

Proof of the graph removal lemma

The triangle removal lemma was extended to general subgraphs by Erdős, Frankl, and Rödl in 1986.[7] 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[5] and to hypergraphs.[4] 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.[1]

A version for induced subgraphs was proved by Alon, Fischer, Krivelevich, and Szegedy in 2000.[8] It states that for any graph ${\displaystyle H}$ with ${\displaystyle h}$ vertices and ${\displaystyle \epsilon >0}$, there exists a constant ${\displaystyle \delta >0}$ such that if an ${\displaystyle n}$-vertex graph ${\displaystyle G}$ has fewer than ${\displaystyle \delta n^{h}}$ induced subgraphs isomorphic to ${\displaystyle H}$, then it is possible to eliminate all induced copies of ${\displaystyle H}$ by adding or removing fewer than ${\displaystyle \epsilon n^{2}}$ 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 ${\displaystyle G}$, 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.[8]

Applications

• Ruzsa and Szemerédi formulated the triangle removal lemma to provide subquadratic upper bounds on the Ruzsa–Szemerédi problem on the size of graphs in which every edge belongs to a unique triangle. This leads to a proof of Roth's theorem.[3]
• The triangle removal lemma can also be used to prove the corners theorem, which states that any subset of ${\displaystyle [n]^{2}}$ which contains no axis-aligned isosceles right triangle has size ${\displaystyle o(n^{2})}$.[9]
• The hypergraph removal lemma can be used to prove Szemerédi's theorem on the existence of long arithmetic progressions in dense subsets of integers.[4]
• The graph removal lemma has applications for property testing, because it implies that for every graph, either the graph is near an ${\displaystyle H}$-free graph, or random sampling will easily find a copy of ${\displaystyle H}$ in the graph.[5] One result is that for any fixed ${\displaystyle \epsilon >0}$, there is a constant time algorithm that returns with high probability whether or not a given ${\displaystyle n}$-vertex graph ${\displaystyle G}$ is ${\displaystyle \epsilon }$-far from being ${\displaystyle H}$-free.[10] Here, ${\displaystyle \epsilon }$-far from being ${\displaystyle H}$-free means that at least ${\displaystyle \epsilon n^{2}}$ edges must be removed to eliminate all copies of ${\displaystyle H}$ in ${\displaystyle G}$.
• The induced graph removal lemma was formulated by Alon, Fischer, Krivelevich, and Szegedy to characterize testable graph properties.[8]

References

1. Fox, Jacob (2011), "A new proof of the graph removal lemma", Annals of Mathematics, Second Series, 174 (1): 561–579, arXiv:1006.1300, doi:10.4007/annals.2011.174.1.17, MR 2811609
2. Trevisan, Luca (May 13, 2009), "The Triangle Removal Lemma", in theory
3. Roth, K. F. (1953), "On certain sets of integers", Journal of the London Mathematical Society, 28 (1): 104–109, doi:10.1112/jlms/s1-28.1.104, MR 0051853
4. Tao, Terence (2006), "A variant of the hypergraph removal lemma", Journal of Combinatorial Theory, Series A, 113 (7): 1257–1280, arXiv:math/0503572, doi:10.1016/j.jcta.2005.11.006, MR 2259060
5. Alon, Noga; Shapira, Asaf (2004), "Testing subgraphs in directed graphs", Journal of Computer and System Sciences, 69 (3): 353–382, doi:10.1016/j.jcss.2004.04.008, MR 2087940
6. Ruzsa, I. Z.; Szemerédi, E. (1978), "Triple systems with no six points carrying three triangles", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, 18, Amsterdam and New York: North-Holland, pp. 939–945, MR 0519318
7. Erdős, P.; Frankl, P.; Rödl, V. (1986), "The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent", Graphs and Combinatorics, 2 (2): 113–121, doi:10.1007/BF01788085, MR 0932119
8. Alon, Noga; Fischer, Eldar; Krivelevich, Michael; Szegedy, Mario (2000), "Efficient testing of large graphs", Combinatorica, 20 (4): 451–476, doi:10.1007/s004930070001, MR 1804820
9. Solymosi, J. (2003), "Note on a generalization of Roth's theorem", Discrete and Computational Geometry, Algorithms and Combinatorics, 25: 825–827, doi:10.1007/978-3-642-55566-4_39, ISBN 978-3-642-62442-1, MR 2038505, S2CID 53973423
10. Alon, Noga; Shapira, Asaf (2008), "A characterization of the (natural) graph properties testable with one-sided error", SIAM Journal on Computing, 37 (6): 1703–1727, doi:10.1137/06064888X, MR 2386211