Skip to main content

Section 5.2 The Regularity and Triangle Removal Lemmas

We will now state the Regularity Lemma and highlight its utility with some applications. The proof will be postponed until Section 5.3.
described in detail following the image
“Triangles.”

Remark 5.2.2.

Without a doubt, the most crucial (and surprising) aspect of the Regularity Lemma is that the upper bound \(k_0(\varepsilon,t)\) on the number of sets in the partition depends only on the parameters \(\varepsilon\) and \(t\text{;}\) in particular, it is independent of the graph \(G\text{.}\)
As a first application, let us see how we can derive the Erdős–Stone Theorem from Turán’s Theorem and the Regularity Lemma.

Another Proof of Theorem 3.3.10.

WRITE THIS.
Next, we will derive a somewhat more profound result, known as the Triangle Removal Lemma. Essentially, this says that a graph with \(n\) vertices and \(o(n^3)\) triangles can be made triangle-free by removing \(o(n^2)\) edges. Do not be fooled by its innocent statement; this is an important result with a wide range of consequences.

Proof.

We prove the contrapositive. Let \(\delta>0\) and let \(G\) be a graph which cannot be made triangle-free by deleting at most \(\delta |V(G)|^2\) edges. Define
\begin{equation*} \varepsilon:=\delta/10 \end{equation*}
and
\begin{equation*} t = \lceil 1/\delta\rceil \end{equation*}
and let
\begin{equation*} \gamma:= \frac{(1-2\varepsilon)\varepsilon^3}{k_0(\varepsilon,t)^3} \end{equation*}
where \(k_0(\varepsilon,t)\) is as in Theorem 5.2.1. Note that, since both \(\varepsilon\) and \(t\) are defined in terms of \(\delta\text{,}\) and \(k_0(\varepsilon,t)\) is a function of \(\varepsilon\) and \(t\text{,}\) we have that \(\gamma\) is a function of \(\delta\text{.}\) Let \(X_1,\dots,X_k\) be the partition of \(V(G)\) obtained by applying Theorem 5.2.1 to \(G\) with parameters \(\varepsilon\) and \(t\text{.}\) Let \(G'\) be the graph obtained from \(G\) by deleting
  • every edge between \(X_i\) and \(X_j\) such that the pair \((X_i,X_j)\) is not \(\varepsilon\)-regular,
  • every edge between \(X_i\) and \(X_j\) such that \(d(X_i,X_j)\lt 2\varepsilon\) and
  • every edge fully contained within \(X_i\) for \(1\leq i\leq k\text{.}\)
The number of edges deleted in the first step is at most
\begin{equation*} \varepsilon\binom{k}{2}\left\lceil\frac{|V(G)|}{k}\right\rceil^2 \lt \varepsilon|V(G)|^2\text{.} \end{equation*}
Similarly, the number deleted in the second step is at most
\begin{equation*} 2\varepsilon k^2\left\lceil\frac{|V(G)|}{k}\right\rceil^2 \lt 4\varepsilon |V(G)|^2\text{.} \end{equation*}
Finally, the number deleted in the third step is at most
\begin{equation*} \sum_{i=1}^k\binom{|X_i|}{2} \leq t\left(\frac{(|V(G)|/t)^2}{2}\right)\leq |V(G)|/2t\text{.} \end{equation*}
Thus, the number of edges removed is at most
\begin{equation*} \left(5\varepsilon +\frac{1}{2t}\right)|V(G)|^2\leq \delta|V(G)|^2\text{.} \end{equation*}
By definition of \(G\text{,}\) the graph \(G'\) still contains a triangle, say \(xyz\text{.}\) By construction of \(G'\text{,}\) we must have \(x\in X_a\text{,}\) \(y\in X_b\) and \(z\in X_c\) for some distinct indices \(a,b\) and \(c\) such that the pairs \((X_a,X_b),(X_a,X_c)\) and \((X_b,X_c)\) are all \(\varepsilon\)-regular with density at least \(2\varepsilon\text{.}\) However, by Lemma 5.1.7, the number of triangles with one vertex in each of the sets \(X_a,X_b\) and \(X_c\) is at least
\begin{equation*} (1-2\varepsilon)\varepsilon^3|X_a||X_b||X_c|\geq \left(\frac{(1-2\varepsilon)\varepsilon^3}{k_0(\varepsilon,t)^3}\right)|V(G)|^3 = \gamma|V(G)|^3\text{.} \end{equation*}
This completes the proof.
The following corollary of the Triangle Removal Lemma is particularly useful; after proving it, we will illustrate it with a couple of applications. Basically, this says that if \(G\) is a graph with \(n\) vertices in which every edge is contained in at most one triangle, then the number of triangles is \(o(n^2)\text{.}\)

Proof.

Let \(\delta=\varepsilon/\ell\) and let \(\gamma=\gamma(\delta)\) be as in Lemma 5.2.3. We set
\begin{equation*} n_0:=\left\lceil\frac{\ell}{6\gamma}\right\rceil\text{.} \end{equation*}
Let \(G\) be any graph with \(n\geq n_0\) vertices such that every edge of \(G\) is contained in at most \(\ell\) triangles. Let \(t(G)\) be the number of triangles in \(G\)
The proof has two steps; first, we prove a weaker upper bound on the number of triangles, and then we strengthen it. Firstly, for each edge \(e\) of \(G\text{,}\) let \(t(e)\) be the number of triangles in \(G\) containing \(e\text{.}\) By assumption, we have \(t(e)\leq \ell\) for every edge. The sum \(\sum_{e\in E(G)}t(e)\) counts every triangle of \(G\) exactly three times. Therefore,
\begin{equation*} 3t(G)=\sum_{e\in E(G)}t(e)\leq \ell|E(G)| \end{equation*}
which implies that
\begin{equation*} t(G)\leq \frac{\ell}{3}\binom{n}{2}\lt \frac{\ell\cdot n^2}{6} = \frac{\ell\cdot n^3}{6n} \leq \frac{\ell\cdot n^3}{6n_0}\leq \gamma n^3\text{.} \end{equation*}
Therefore, by the Triangle Removal Lemma, \(G\) can be made triangle-free by removing at most \(\delta n^2\) edges. However, each edge \(e\) that is removed reduces the number of triangles by at most \(t(e)\leq \ell\text{.}\) Therefore, the total number of triangles which were contained in \(G\) to begin with must have been at most \(\ell\delta n^2 = \varepsilon n^2\text{.}\)
As our first application of Corollary 5.2.4, let us derive the well-known \((6,3)\)-Theorem. The following can be seen as an upper bound for a Turán-type problem in \(3\)-uniform hypergraphs where multiple different subhypergraphs are being forbidden.

Proof.

Let \(n_0\) be equal to \(n_0(\varepsilon,2)\) from Corollary 5.2.4. Let \(H\) be a \(3\)-uniform hypergraph with \(n\geq n_0\) vertices in which there is no set of six vertices containing at least three hyperedges. We let \(G\) be the graph with \(V(G)=V(H)\) where \(uv\) is an edge of \(G\) if and only if there is a hyperedge in \(H\) containing \(u\) and \(v\text{.}\) Note that every hyperedge in \(H\) corresponds to a triangle in \(G\text{,}\) and so it suffices to show that \(G\) has at most \(\varepsilon n^2\) triangles.
To do this, we will show that no edge of \(G\) is contained in more than two triangles of \(G\text{,}\) from which the result will follow by Corollary 5.2.4. Let \(uv\) be any edge of \(G\text{;}\) our goal is to show that it is contained in at most two triangles. We break the proof into two cases; see Figure 5.2.6 for an illustration.

Case.

There exist \(e,e'\in E(H)\) such that \(\{u,v\}\subseteq e\) and \(|e\cap e'|=2\text{.}\)
We claim that there cannot exist a third hyperedge \(e''\in E(H)\setminus\{e,e'\}\) such that \(e\cap e''\neq \emptyset\text{.}\) If such an \(e''\) did exist, then \(e\cup e'\cup e''\) would be a set of at most \(6\) vertices containing at least three distinct hyperedges of \(H\) (namely, \(e,e'\) and \(e''\)) which would contradict our assumption on \(H\text{.}\)
This implies that the four vertices of \(e\cup e'\) have no neighbours outside of \(e\cup e'\) and, moreover, that there is no edge in \(G\) from the unique vertex of \(e\setminus e'\) to the unique vertex of \(e'\setminus e\text{.}\) Consequently, we get that the edge in \(e\cap e'\) is contained in precisely two triangles and that all other edges in \(e\cup e'\) are contained in only one triangle; in particular, \(uv\) is contained in at most two triangles.

Case.

For every hyperedge \(e\) containing \(u\) and \(v\) and \(e'\in E(H)\setminus \{e\}\text{,}\) it holds that \(|e\cap e'|\leq 1\text{.}\)
Let \(e\) be any hyperedge containing \(u\) and \(v\) (which must exist, by definition of \(G\)). Suppose that there exists a vertex \(x\notin e\) such that \(\{u,v,x\}\) forms a triangle in \(G\text{.}\) Then there must exist hyperedges \(e'\) and \(e''\) such that \(u,x\in e'\) and \(v,x\in e''\text{.}\) By assumption, we must have \(e\cap e'=\{u\}\) and \(e\cap e''=\{v\}\text{;}\) in particular, \(e,e'\) and \(e''\) are all distinct. The set \(e\cup e'\cup e''\) is now a set of at most six vertices containing three distinct hyperedges, which is again a contradiction. This completes the proof.
Figure 5.2.6. An illustration of the two cases in the proof of Theorem 5.2.5. Both of these configurations clearly consist of at most six vertices and at least three hyperedges.
Another application of Corollary 5.2.4 is Roth’s Theorem from combinatorial number theory. Essentially, this theorem says that any subset of \([n]\) without a non-trivial \(3\)-term arithmetic progression has \(o(n)\) elements; the following definition explains what we mean by this.

Definition 5.2.7.

A sequence \((a_1,a_2,\dots,a_k)\) of integers is called a \(k\)-term arithmetic progression if there exists \(d\geq 0\) such that
\begin{equation*} a_{i+1}-a_i=d \end{equation*}
for all \(1\leq i\leq k-1\text{.}\) It is trivial if \(d=0\) and non-trivial otherwise.

Proof.

For \(0\lt \delta\lt 1\text{,}\) define
\begin{equation*} \varepsilon=\frac{\delta}{81} \end{equation*}
and let \(N_0:= n_0(\varepsilon,1)/9\) where \(n_0\) is as in Corollary 5.2.4. For \(n\geq n_0\text{,}\) we suppose that there exists \(A\subseteq [n]\) of cardinality at least \(\delta n\) without any non-trivial \(3\)-term arithmetic progression and derive a contradiction.
Let us start by building a graph \(G\) based on \(A\) as follows. Let \(X=\{x_0,\dots,x_{3n}\}\text{,}\) \(Y=\{y_0,\dots,y_{3n}\}\) and \(Z=\{z_0,\dots,z_{3n}\}\) be disjoint sets of vertices.
  • Add an edge from \(x_i\) to \(y_j\) if \(j-i\in A\text{.}\)
  • Add an edge from \(y_i\) to \(z_j\) if \(j-i\in A\text{.}\)
  • Add an edge from \(x_i\) to \(z_j\) if \((j-i)/2\in A\text{.}\)
(Note that, here, all arithmetic is viewed modulo \(3n+1\)).
Let \(t(G)\) denote the number of triangles in \(G\text{.}\) For \(a\in A\) and \(b\in\{0,\dots,n\}\text{,}\) we have that \(x_b,y_{b+a},z_{b+2a}\) forms a triangle in \(G\text{,}\) by construction. Therefore,
\begin{equation*} t(G) \geq |A|(n+1) > \frac{\delta |V(G)|^2}{81} = \varepsilon |V(G)|^2\text{.} \end{equation*}
(Here, we used that \(|V(G)|=9n+3\) and \(|A|\geq \delta n\)).
Now, we will show that every edge of \(G\) is contained in at most one triangle. If this is true, then, by Corollary 5.2.4 and the fact that \(|V(G)|\geq 9n \geq n_0(\varepsilon,1)\text{,}\) we will have that \(G\) contains at most \(\varepsilon|V(G)|^2\) triangles, which will contradict the lower bound on the number of triangles proved above; thus, the proof will be complete.
Consider any triangle \(x_i,y_j,z_k\) in \(G\) with \(x_i\in X,y_j\in Y\) and \(z_k\in Z\text{.}\) By construction, we must have
\begin{equation*} j-i\in A\text{,} \end{equation*}
\begin{equation*} \frac{k-i}{2}\in A \end{equation*}
and
\begin{equation*} k-j\in A\text{.} \end{equation*}
Thus, \(j-i,\frac{k-i}{2}\) and \(k-j\) form a \(3\)-term arithmetic progression in \(A\) with common difference \(\frac{i-2j+k}{2}\text{.}\) Since we are assuming that all \(3\)-term arithmetic progressions in \(A\) are trivial, we must have
\begin{equation} i-2j+k=0\text{.}\tag{5.2.1} \end{equation}
Thus, for any choice of two of \(i,j,k\text{,}\) the third is uniquely determined. Thus, every edge of \(G\) is contained in at most one triangle and we are done.
Figure 5.2.9. An illustration of the graph \(G\) constructed in the proof of Roth’s Theorem.
Here are a few of YouTube videos related to the Regularity and Triangle Removal Lemmas: