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

An alternative way to state this is to say that for any $n$-vertex graph $G$ with $o(n^{h})$ subgraphs isomorphic to $H$, it is possible to eliminate all copies of $H$ by removing $o(n^{2})$ edges from $G$. Here, the $o$ indicates the use of little o notation.

In the case when $H$ 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 $n$ vertices contains $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 Ruzsa–Szemerédi problem to arbitrary $r$-uniform graphs, Erdős, Frankl, and Rödl provided statement for general graphs very close to the modern graph removal lemma: if graph $H_{2}$ is a homomorphic image of $H_{2}$, then any $H_{1}$-free graph $G$ on $n$ vertices can be made $H_{2}$-free by removing $o(n^{2})$ 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 $H$ be a graph on $h$ vertices, whose vertex set is $V=\{1,2,\ldots ,h\}$ and edge set is $E$. Let $X_{1},X_{2},\ldots ,X_{h}$ be sets of vertices of some graph $G$ such that for all $ij\in E$ pair $(X_{i},X_{j})$ is $\epsilon$-regular (in the sense of regularity lemma). Let also $d_{ij}$ be the density between sets $X_{i}$ and $X_{j}$. Intuitively, regular pair $(X,Y)$ with density $d$ should behave like a random Erdős–Rényi-like graph, where every pair of vertices $(x,y)\in (X\times Y)$ is selected to be an edge independently with probability $d$. This suggests that the number of copies of $H$ on vertices $x_{1},x_{2},\ldots ,x_{h}$ such that $x_{i}\in X_{i}$ should be close to the expected number from Erdős–Rényi model:

$$\prod _{ij\in E(H)}d_{ij}\prod _{i\in V(H)}|X_{i}|$$

where $E(H)$ and $V(H)$ are the edge set and the vertex set of $H$.

Precise statement

The straightforward formalization of above heuristic claim is as follows. Let $H$ be a graph on $h$ vertices, whose vertex set is $V=\{1,2,\ldots ,h\}$ and edge set is $E$. Let $\delta >0$ be arbitrary. Then there exists $\epsilon >0$ such that for any $X_{1},X_{2},\ldots ,X_{h}$ as above, satisfying $d_{ij}>\delta$ for all $ij\in E$, the number of graph homomorphisms from $H$ to $G$ such that vertex $i\in V(H)$ is mapped to $X_{i}$ is not smaller than

$$(1-\delta )\prod _{ij\in E}(d_{ij}-\delta )\prod _{i\in V}|X_{i}|$$

Blow-up Lemma

One can even find bounded degree subgraphs of blow-ups of $H$ 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 $H_{1}$ be an arbitrary graph and $t\in \mathbb {Z} _{+}$. Construct $H(t)$ by replacing each vertex $i$ of $H$ by independent set $V_{i}$ of size $t$ and replacing every edge $ij$ of $H$ by complete bipartite graph on $(V_{i},V_{j})$. Let $\epsilon ,\delta >0$ be arbitrary reals, $N$ be a positive integer and let $H_{2}$ be a subgraph of $H(t)$ with $h$ vertices and with maximum degree $\Delta$. Define $\epsilon _{0}=\delta ^{\Delta }/(2+\Delta )$. Finally, let $G$ be a graph and $X_{1},X_{2},\ldots ,X_{h}$ be disjoint sets of vertices of $G$ such that whenever $ij\in E(H_{2})$ then $(X_{i},X_{j})$ is a $\epsilon$-regular pair with density at least $\epsilon +\delta$. Then if $\epsilon \leq \epsilon _{0}$ and $1-t\leq N\epsilon _{0}$, the number of injective graph homomorphisms from $H_{2}$ to $G$ is at least $(\epsilon _{0}N)^{h}$.

In fact, one can only restrict to counting homomorphisms such that any vertex $k\in [h]$ of $H_{2}$ such that $k\in V_{i}$ is mapped to a vertex in $X_{i}$.

Proof

We will provide proof of the counting lemma in the case when $H$ 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 $\epsilon =\delta /2$. Let $X_{1}'\subset X_{1}$ be the set of those vertices in $X_{1}$ which have at least $(d_{12}-\epsilon )|X_{2}|$ neighbors in $X_{2}$ and at least $(d_{13}-\epsilon )|X_{3}|$ neighbors in $X_{3}$. Note that if there were more than $\epsilon |X_{1}|$ vertices in $X_{1}$ with less than $(d_{12}-\epsilon )|X_{2}|$ neighbors in $X_{2}$, then these vertices together with whole $X_{2}$ would witness $\epsilon$-irregularity of the pair $(X_{1},X_{2})$. Repeating this argument for $X_{3}$ shows that we must have $|X_{1}'|>(1-2\epsilon )|X_{1}|$. Now take arbitrary $x\in X_{1}'$ and define $X_{2}'$ and $X_{3}'$ as neighbors of $x$ in $X_{2}$ and $X_{3}$ respectively. By definition $|X_{2}'|\geq (d_{12}-\epsilon )|X_{2}|\geq \epsilon |X_{2}|$ and $|X_{3}'|\geq \epsilon |X_{3}|$ so by regularity of $(X_{2},X_{3})$ we obtain existence of at least

$$(d_{23}-\epsilon )|X_{2}'||X_{3}'|\geq (d_{12}-\epsilon )(d_{23}-\epsilon )(d_{13}-\epsilon )|X_{2}||X_{3}|$$

triangles containing $x$. Since $x$ was chosen arbitrarily from the set $X_{1}'$ of size at least $(1-2\epsilon )|X_{1}|$, we obtain a total of at least

$$(1-2\epsilon )(d_{23}-\epsilon )|X_{2}'||X_{3}'|\geq (d_{12}-\epsilon )(d_{23}-\epsilon )(d_{13}-\epsilon )|X_{1}||X_{2}||X_{3}|$$

which finishes the proof as $\epsilon =\delta /2$.

Proof

Proof of the triangle removal lemma

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

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

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

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

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

$$\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 proof of the case of general $H$ 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 $G$ is considered to contain an induced subgraph $H$ if there is an injective map $f:V(H)\rightarrow V(G)$ such that $(f(u),f(v))$ is an edge of $G$ if and only if $(u,v)$ is an edge of $H$. Notice that non-edges are considered as well. $G$ is induced $H$-free if there is no induced subgraph $G$. We define $G$ as $\epsilon$-far from being induced $H$-free if we cannot add or delete $\epsilon n^{2}$ edges to make $G$ induced $H$-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 $H$ with $h$ vertices and $\epsilon >0$, there exists a constant $\delta >0$ such that if an $n$-vertex graph $G$ has fewer than $\delta n^{h}$ induced subgraphs isomorphic to $H$, then it is possible to eliminate all induced copies of $H$ by adding or removing fewer than $\epsilon n^{2}$ edges.

The problem can be reformulated as follows: Given a red-blue coloring $H'$ of the complete graph $K_{h}$ (Analogous to the graph $H$ on the same $h$ vertices where non-edges are blue, edges are red), and a constant $\epsilon >0$, then there exists a constant $\delta >0$ such that for any red-blue colorings of $K_{n}$ has fewer than $\delta n^{h}$ subgraphs isomorphic to $H'$, then it is possible to eliminate all copies of $H$ by changing the colors of fewer than $\epsilon n^{2}$ 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 $\epsilon _{0}\geq \epsilon _{1}\geq ...>0$, there exists an integer $M$ such that for any graph $G$, we can obtain two (equitable) partitions ${\mathcal {P}}$ and ${\mathcal {Q}}$ such that the following properties are satisfied:

• ${\mathcal {Q}}$ refines ${\mathcal {P}}$, that is every part of ${\mathcal {P}}$ is the union of some collection of parts in ${\mathcal {Q}}$.
• ${\mathcal {P}}$ is $\epsilon _{0}$-regular and ${\mathcal {Q}}$ is $\epsilon _{|{\mathcal {P}}|}$-regular.
• $q({\mathcal {Q}})<q({\mathcal {P}})+\epsilon _{0}$
• $|{\mathcal {Q}}|\leq M$

The function $q$ is defined to be the energy function defined in Szemerédi regularity lemma. Essentially, we can find a pair of partitions ${\mathcal {P}},{\mathcal {Q}}$ where ${\mathcal {Q}}$ is extremely regular compared to ${\mathcal {P}}$, and at the same time ${\mathcal {P}},{\mathcal {Q}}$ 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 $\epsilon _{0}\geq \epsilon _{1}\geq ...>0$, there exists $\delta >0$ such that there exists a partition ${\mathcal {P}}={V_{1},...,V_{k}}$ and subsets $W_{i}\subset V_{i}$ for each $i$ where the following properties are satisfied:

• $|W_{i}|>\delta n$
• $(W_{i},W_{j})$ is $\epsilon _{|{\mathcal {P}}|}$-regular for each pair $i,j$
• $|d(W_{i},W_{j})-d(V_{i},V_{j})|\leq \epsilon _{0}$ for all but $\epsilon _{0}|{\mathcal {P}}|^{2}$ pairs $i,j$

The main idea of the proof of this corollary is to start with two partitions ${\mathcal {P}}$ and ${\mathcal {Q}}$ that satisfy the Strong Regularity Lemma where $q({\mathcal {Q}})<q({\mathcal {P}})+\epsilon _{0}^{3}/8$. Then for each part $V_{i}\in {\mathcal {P}}$, we uniformly at random choose some part $W_{i}\subset V_{i}$ that is a part in ${\mathcal {Q}}$. The expected number of irregular pairs $(W_{i},W_{j})$ is less than 1. Thus, there exists some collection of $W_{i}$ such that every pair is $\epsilon _{|{\mathcal {P}}|}$-regular!

The important aspect of this corollary is that every pair of $W_{i},W_{j}$ are $\epsilon _{|{\mathcal {P}}|}$-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 $G$ with $n$ vertices that has less than $\delta n^{v(H)}$ copies of $H$. The idea is to start with a collection of vertex sets $W_{i}$ 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 $(W_{i},W_{j})$ with low density, and we can add all edges between pairs of parts $(W_{i},W_{j})$ with high density. We choose the density requirements such that we added/deleted at most $\epsilon n^{2}$ edges.

If the new graph has no copies of $H$, then we are done. Suppose the new graph has a copy of $H$. Suppose the vertex $v_{i}\in v(H)$ is embedded in $W_{f(i)}$. Then if there is an edge connecting $v_{i},v_{j}$ in $H$, then $W_{i},W_{j}$ does not have low density. (Edges between $W_{i},W_{j}$ were not removed in the cleaning process) Similarly, if there is not an edge connecting $v_{i},v_{j}$ in $H$, then $W_{i},W_{j}$ does not have high density. (Edges between $W_{i},W_{j}$ 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 $G$ has more than $\delta n^{v(H)}$ copies of $H$.

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 $\delta$ to be extremely small, bounded by tower function of height polynomial in $\epsilon ^{-1}$ that is $\delta =1/{\text{tower}}(\epsilon ^{-O(1)})$ (here ${\text{tower}}(k)$ is the tower of twos of height $k$). Tower function of height $\epsilon ^{-O(1)}$ 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 $\delta =1/{\text{tower}}(5h^{2}\log \epsilon ^{-1})$ (here $h$ is number of vertices of removed graph $H$). 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 $H$ it was shown that $\delta =\epsilon ^{O(1)}$ is sufficient.

There is a large gap between upper and lower bounds for $\delta$ in the general case. The current best result true for all graphs $H$ is due to Alon and states that for each nonbipartite $H$ there exists constant $c>0$ such that $\delta <(\epsilon /c)^{c\log(c/\epsilon )}$ is necessary for the graph removal lemma to hold while for bipartite $H$ the optimal $\delta$ has polynomial dependence on $\epsilon$, 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 $\delta$ in the triangle removal lemma. This method can be leveraged for arbitrary nonbipartite $H$ to give aforementioned bound.

Applications

Additive combinatorics

• 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.
• The triangle removal lemma can also be used to prove the corners theorem, which states that any subset of $[n]^{2}$ which contains no axis-aligned isosceles right triangle has size $o(n^{2})$.
• 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.

Graph theory

• Graph counting/removal lemma can be used to provide quick and transparent proof of Erdős–Stone theorem starting from Turán's theorem and extend the result to Simonovits stability: for any graph $H$ and any $\epsilon >0$ there exists $\delta$ such that any $H$-free graph on $n$ vertices with at least $\left(1-{\frac {1}{\chi (H)-1}}\right){\binom {n}{2}}-\delta n^{2}$ edges can be transformed into complete $(\chi (H)-1)$-partite Turán graph $T_{n,\chi (H)-1}$ by adding and/or deleting at most $\epsilon n^{2}$ edges (here $\chi (H)$ is the chromatic number of $H$). Although both results had been proven earlier using more elementary techniques (Erdős–Stone theorem was proved in 1966 by Erdős and Stone while Simonovits stability was shown in the same year by various authors), the regularity proof provides different viewpoint and elucidates connection with other modern proofs.
• Graph removal lemma together with Erdős–Stone theorem may be used to show that the number of non-isomorphic $H$-free graphs on $n$ vertices is equal to
  $$2^{(\pi (H)+o(1)){\binom {n}{2}}}$$
  where $\pi (H)=1-{\frac {1}{\chi (H)-1}}$ is the Turán density of $H$.

Property testing

• The graph removal lemma has applications for property testing, because it implies that for every graph, either the graph is near an $H$-free graph, or random sampling will easily find a copy of $H$ in the graph. One result is that for any fixed $\epsilon >0$, there is a constant time algorithm that returns with high probability whether or not a given $n$-vertex graph $G$ is $\epsilon$-far from being $H$-free. Here, $\epsilon$-far from being $H$-free means that at least $\epsilon n^{2}$ edges must be removed to eliminate all copies of $H$ in $G$.
• The induced graph removal lemma was formulated by Alon, Fischer, Krivelevich, and Szegedy to characterize testable graph properties.

See also

• Counting lemma
• Tuza's conjecture