Applications of Szemerédi's regularity lemma: triangle removal lemma, Roth's theorem, corner's theorem and graph removal lemma

In the previous post we proved Szemerédi’s regularity lemma, and now we give a few of its various applications: the triangle removal lemma, Roth’s theorem on the existence of arithmetic progressions of length in subsets of the integers with positive density, the corner’s theorem and, finally, the graph removal lemma.

1. Triangle removal lemma

Most applications of Szemerédi’s regularity lemma deal with monotone problems, when throwing in more edges can only help. In these applications, one starts applying the original form of the regularity lemma to create a regular partition, then gets rid of all edges within the clusters of the partition, also the edges of non-regular pairs as well as those of regular pairs with small density. The leftover “pure” graph is much easier to handle and still contains most of the original edges. This is what happens in proving the triangle removal lemma.

The triangle removal lemma is the (intuitive, yet nontrivial) fact that if one has to delete at least edges of a graph with vertices to destroy all triangles in it, then the graph must contain at least triangles, where . If one only thinks naively, the conclusion is that the graph contains at least triangles, and the strength of the triangle removal lemma is that, instead of quadratic, the number of triangles is cubic. It was first proved by Ruzsa and Szemerédi in the paper Triple systems with no six points carrying three triangles, who also observed it implies Roth’s theorem, as we shall see in the next section.

Definition 1 Given , a graph is -far from being triangle free if one has to delete at least edges of to destroy all triangles in it.

In particular, every graph that is -far from being triangle-free has at least one triangle (indeed, at least of them).

Theorem 2 (Triangle removal lemma) For any , there is such that, whenever is -far from being triangle-free, then it contains at least triangles.

Proof: Let be an -far from being triangle-free graph and . We can assume by just taking sufficiently small so that

Consider the -regular partition given by Szemerédi’s regularity lemma. Let and the graph obtained from by deleting the following edges:

1. All edges incident in : there are at most edges.
2. All edges inside the clusters : the number of edges is at most

   

3. All edges that lie in irregular pairs: there are less than

   

   edges.

4. All edges lying in a pair of clusters whose density is less than : their cardinality is at most

   

The number of deleted edges is less than and so contains a triangle. The three vertices of such triangle belong to three remaining distinct clusters, let us say . We’ll show that in fact these clusters support many triangles.

Call a vertex typical if it has at least adjacent vertices in and at least adjacent vertices in . As, by hypothesis,

whenever , have cardinality at least , there are more than typical vertices in . In fact, the number of vertices in with at least adjacent vertices in is greater than . If this were not the case, the subset of non-typical vertices would have more than elements and would satisfy

contradicting (1). As the same argument holds to , the number of typical vertices in is at least

Let be one of them and consider the vertices adjacent to .

Every edge between and generates a triangle. Observe that this number is at least

Summing this up in typical, has at least triangles. Because , this quantity is greater or equal to

1.1. Roth’s theorem

As an application of the triangle removal lemma, we prove Roth’s theorem proved in On certain sets of integers.

Theorem 3 (Roth) If has positive upper density, then it contains an arithmetic progression of length .

Proof: Assume that

Consider a graph in the following way:

1. , where have vertices labeled from 1 to each.
2. There is an edge from to iff .
3. There is an edge from to iff .
4. There is an edge from to iff .

Then form a triangle exists iff

that is, the triangles identify arithmetic progressions of length 3 in , including the trivial ones , . There are more than of these trivial triangles and they are all disjoint. This mere disjointness implies is -far from being triangle-free and so, by the triangle removal lemma, has at least triangles of which at least are non-trivial. The proof is complete by taking .

1.2. Corner’s theorem

This result was first proved by Ajtai and Szemerédi in Sets of lattice points that form no squares. The simpler proof we present here, using the triangle removal lemma, was obtained by Solymosi in Note on a generalization of Roth’s theorem. We point out, and leave the proof to the reader, that the corner’s theorem is a strengthening of Roth’s theorem.

Definition 4 A corner is an axis-aligned isosceles triangle of , that is, it is a set of three different elements of of the form

The corner’s theorem states that every set of positive density has a corner.

Theorem 5 (Corner’s theorem) For every , there exists such that any subset of with at least points has a corner.

Proof: We proceed similarly to the proof of Roth’s theorem. Let be a subset of with at least points and consider the tripartite graph defined by:

1. , where and represent the horizontal, vertical and diagonal lines of respectively.
2. There is an edge from a line of to a line of iff the intersection of the two lines belongs to .

has vertices. The triangles of correspond to the corners of , including the trivial ones . has more than of these trivial triangles and they are all disjoint, so that is -far from being triangle-free. By the triangle removal lemma, has at least triangles of which at least are non-trivial and give the required corner.

 

2. Graph removal lemma

The triangle removal lemma asserts that every graph for which it is necessary to throw a positive fraction of edges in order to destroy all triangles indeed has a positive fraction of triangles. The fact is that, as proved by Erdös, Frankl and Rödl in The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, instead of fixing the triangle configuration, the result is also true for any fixed configuration. More formally, let be a finite graph with vertices and, analogously, consider the following

Definition 6 Given , a graph is -far from being -free if one has to delete at least edges of to destroy all copies of in it.

Theorem 7 (Graph removal lemma) For any , there is such that, whenever is -far from being -free, then it contains at least copies of .

The proof of this theorem is more intricate than that of the triangle removal lemma. Actually, it depends on the structure of the graph . If, for example, is a four-cycle, then the argument applied in the proof of the triangle removal lemma does not work, mainly because, once the “impure” edges are discarded, the copy of that remains may have two vertices in a same cluster. In other words, the connectivity properties of influence the distribution of the vertices along the clusters in a potential candidate for copy of in . As in the triangle removal lemma, this problem does not occur if is the complete graph in vertices. For this reason, the proof of the graph removal lemma will be accomplished in three parts:

Part 1. The establishment of the graph removal lemma for .

Part 2. We observe that, for a general , the application of the same idea in Part 1 only guarantees the existence of clusters, where is the chromatic number of .

Part 3. If we apply the same idea as in Part 1, allowing the choice of more than one vertex in a same cluster, we obtain the result for any .

As remarked above, Part 1 follows the same lines of the proof of the triangle removal lemma: we clean out the graph and the remaining copy of is supported in different clusters, which indeed contain many copies of . The construction of many copies is again accomplished by the typicality of most of the vertices, and is given by the following

Lemma 8 If is -regular and , then at least vertices of are adjacent to at least vertices of .

Proof: Let . Then

If , the -regularity guarantees that

thus contradicting (2).

Proof of the graph removal lemma for : Let be -far from being -free graph with , and consider the -regular partition given by Szemerédi’s regularity lemma. Let and the graph obtained from by deleting the following edges:

1. All edges incident in : there are at most edges.
2. All edges inside the clusters : the number of edges is at most

   

3. All edges that lie in irregular pairs: there are less than

   

   edges.

4. All edges lying in a pair of clusters whose density is less than : their cardinality is at most

   

The number of deleted edges is less than and so contains . The vertices of such belong to distinct remaining clusters, say . We’ll show that these clusters support many copies of . This is done in steps, the step consisting of choosing a vertex from in such a way that is adjacent to each of the previously chosen vertices . If there are ways of choosing , where is independent of , then contains at least

copies of and we’re done.

By Lemma 8, at least points in are joined to at least points of for each . Take one such point and denote by the subset of of all the adjacent vertices to , for each . We have

and hence any two of the clusters are -regular and have density at least . This concludes the first step.

We now proceed to step 2: again by Lemma 8, at least points in are joined to at least points of for each . Take one such point and denote by the subset of of all the adjacent vertices to , for each . We have

and hence any two of the clusters are -regular and have density at least .

Assuming, without loss of generality, that and , the above procedure can be repeated times. This concludes the proof.

Now let be an arbitrary graph. The chromatic number of is the smallest number of colors needed to paint the vertices of in such a way that no two adjacent vertices have the same color. Equivalently, it is the smallest for which is -partite, that is, for which one can divide the vertices of into disjoint subsets such that no two vertices on a same subset are adjacent. Let these subsets have cardinality and be the complete -partite graph whose subsets have cardinality . Obviously, contains and so the number of copies of in a given graph is at least the number of copies of .

Observe that if we apply the same idea as in Part 1 to a -far from being -free graph, the remaining copy of has vertices in at least clusters , and not necessarily in different clusters. This is not a problem: instead of choosing one vertex in each , we choose of them. If the same procedure works, each of these choices generates a copy of and thus of . This is how we proceed below.

Proof of the graph removal lemma: Apply the same argument as in Part 1 to obtain clusters such that any pair is -regular and has density at least . We can thus find points of which are joined to at least points of for each . Take one such point and denote by the set of all vertices of which are joined to , for each . Also, set (here is the difference: we don’t discard ). We have

for every and hence each pair among is -regular and has density at least .

Repeating this argument successively times in the first cluster, times in the second cluster, , times in the -th cluster, we construct vertices forming a copy of . This completes the proof.

We point out a recent proof of the graph removal lemma avoiding the use of Szemerédi’s regularity lemma has been obtained by Fox in the paper A new proof of the graph removal lemma. Although it does not use the regularity lemma, its idea is similar. Instead of using the mean square density given by the index

it uses a mean entropy density

where for and . Like in the regularity lemma, whenever a partition does not supports many copies of , Fox shows, using a Jensen defect inequality, that there is a refinement of the partition that increases the mean square entropy a fixed amount.

We finish this post mentioning another version of the graph removal lemma that counts the number of induced graphs. A subgraph of a graph is said to be induced if any pair of vertices of are adjacent if and only if they are adjacent in . For example, has an induced but does not have an induced four-cycle. This shows that induced graphs are harder to find, and actually that the excess of edges might prevent them to exist. In this setting, we have to consider a new definition of -far from being -free, in which one can remove or include edges.

Definition 9 Given , a graph is -unavoidable for if any graph that differs from in no more that edges has an induced copy of .

We thus have the graph removal lemma, proved by Alon, Fischer, Krivelevich and Szegedy in Efficient testing of large graphs.

Theorem 10 (Graph removal lemma for induced graphs) For any , there is such that, whenever is -unavoidable for , then it contains at least induced copies of .

We won’t prove it. Instead, we refer the reader to the original paper.

The content of this and the post Szemerédi’s regularity lemma can be downloaded in PDF format in my lecture notes available at my homepage.

About these ads