Graph removal lemma

Let ${\displaystyle H}$ be a graph on ${\displaystyle h}$ vertices, whose vertex set is ${\displaystyle V=\{1,2,\ldots ,h\}}$ and edge set is ${\displaystyle E}$. Let ${\displaystyle X_{1},X_{2},\ldots ,X_{h}}$ be sets of vertices of some graph ${\displaystyle G}$ such that for all ${\displaystyle ij\in E}$ pair ${\displaystyle (X_{i},X_{j})}$ is ${\displaystyle \epsilon }$-regular (in the sense of regularity lemma). Let also ${\displaystyle d_{ij}}$ be the density between sets ${\displaystyle X_{i}}$ and ${\displaystyle X_{j}}$. Intuitively, regular pair ${\displaystyle (X,Y)}$ with density ${\displaystyle d}$ should behave like a random Erdős–Rényi-like graph, where every pair of vertices ${\displaystyle (x,y)\in (X\times Y)}$ is selected to be an edge independently with probability ${\displaystyle d}$. This suggests that the number of copies of ${\displaystyle H}$ on vertices ${\displaystyle x_{1},x_{2},\ldots ,x_{h}}$ such that ${\displaystyle x_{i}\in X_{i}}$ should be close to the expected number from Erdős–Rényi model:

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

where ${\displaystyle E(H)}$ and ${\displaystyle V(H)}$ are the edge set and the vertex set of ${\displaystyle H}$.

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

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

One can even find bounded degree subgraphs of blow-ups of ${\displaystyle 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.[9] 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.[10]

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

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

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

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

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

$${\displaystyle (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 ${\displaystyle \epsilon =\delta /2}$.

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

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}.}$$

The proof of the case of general ${\displaystyle H}$ is analogous to the triangle case, and uses graph counting lemma instead of triangle counting lemma.

A version of the Graph Removal for induced subgraphs was proved by Alon, Fischer, Krivelevich, and Szegedy in 2000.[12] 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.

The problem can be reformulated as follows: Given a red-blue coloring ${\displaystyle H'}$ of the complete graph ${\displaystyle K_{h}}$ (Analogous to the graph ${\displaystyle H}$ on the same ${\displaystyle h}$ vertices where non-edges are blue, edges are red), and a constant ${\displaystyle \epsilon >0}$, then there exists a constant ${\displaystyle \delta >0}$ such that for any red-blue colorings of ${\displaystyle K_{n}}$ has fewer than ${\displaystyle \delta n^{h}}$ subgraphs isomorphic to ${\displaystyle H'}$, then it is possible to eliminate all copies of ${\displaystyle H}$ by changing the colors of fewer than ${\displaystyle \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.[12]

The strong regularity lemma[12] is a strengthened version of Szemerédi's Regularity Lemma. For any infinite sequence of constants ${\displaystyle \epsilon _{0}\geq \epsilon _{1}\geq ...>0}$, there exists an integer ${\displaystyle M}$ such that for any graph ${\displaystyle G}$, we can obtain two (equitable) partitions ${\displaystyle {\mathcal {P}}}$ and ${\displaystyle {\mathcal {Q}}}$ such that the following properties are satisfied:

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

The function ${\displaystyle q}$ is defined to be the energy function defined in Szemerédi regularity lemma. Essentially, we can find a pair of partitions ${\displaystyle {\mathcal {P}},{\mathcal {Q}}}$ where ${\displaystyle {\mathcal {Q}}}$ is extremely regular compared to ${\displaystyle {\mathcal {P}}}$, and at the same time ${\displaystyle {\mathcal {P}},{\mathcal {Q}}}$ are close to each other. (This property is captured in the third condition)

The following corollary of the strong regularity lemma is used in the proof of the Induced Graph Removal Lemma.[12] For any infinite sequence of constants ${\displaystyle \epsilon _{0}\geq \epsilon _{1}\geq ...>0}$, there exists ${\displaystyle \delta >0}$ such that there exists a partition ${\displaystyle {\mathcal {P}}={V_{1},...,V_{k}}}$ and subsets ${\displaystyle W_{i}\subset V_{i}}$ for each ${\displaystyle i}$ where the following properties are satisfied:

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

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

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

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