Szemerédi’s regularity lemma is an important tool in discrete mathematics, specially in graph theory and additive combinatorics. It says that, in some sense, all graphs can be approximated by random-looking graphs. The lemma helps in proving theorems for arbitrary graphs whenever the corresponding result is easy for random graphs. One of its applications is the triangle removal lemma which, as observed by Ruzsa and Szemerédi in the paper Triple systems with no six points carrying three triangles, gives a proof of Roth’s theorem on the existence of arithmetic progressions of length in subsets of the integers with positive density (see ERT13 for an ergodic theoretical proof).
In this first of two posts, we prove Szemerédi’s regularity lemma. The second post will give some applications of this lemma: the triangle removal lemma and Roth’s theorem. Some of the content has intersection with the Ergodic Ramsey Theory posts, whose interested reader may check here: ERT0, ERT1, ERT2, ERT3, ERT4, ERT5, ERT6, ERT7, ERT8, ERT9, ERT10, ERT11, ERT12, ERT13, ERT14, ERT15, ERT16.
1. Additive combinatorics
“Additive combinatorics is the theory of
counting additive structures in sets.“
T. Tao and V. Vu.
This theory has seen exciting developments and dramatic changes in direction in recent years, thanks to its connections with areas such as number theory, ergodic theory and graph theory. This section gives a brief historic introduction on the main results.
Van der Waerden’s theorem (see ERT6 for a topological dynamical proof), one of Kintchine’s Three Pearls of Number Theory, states that whenever the natural numbers are finitely partitioned (or, as it is customary to say, finitely colored), one of the cells of the partition contains arbitrarily long arithmetic progressions. In other words, the structure of the natural numbers can not be destroyed by partitions: arbitrarily large parts of persist inside some component of the partition. This result was first proved in and represents the first great result on additive combinatorics. Afterwards, in the mid-thirties, Erdös and Turán conjectured a density version of van der Waerden’s theorem. To present it, let us define what is the notion of density in the natural numbers.
Definition 1 Given a set , the upper density of is
If the limit exists, we say that has density, and denote it by . As pointed out by Erdös and Turán, having positive upper density is a notion of largeness and it is natural to ask if sets with this property have arbitrarily long arithmetic progressions. This quite recalcitrant question was only settled in by Szemerédi in the paper On sets of integers containing no elements in arithmetic progressions . Meanwhile, the first partial result was obtained by Roth in .
His proof relied on a Fourier-analytic argument of energy increment for functions: one decomposes a function as , where is good and is bad in a specific sense (this follows the same philosophy of Calderón-Zygmund’s theory on harmonic analysis). If the effect of is large, it is possible to break it into good and bad parts again and so on. In each step, the “energy” of increases a fixed amount. Being bounded, it must stop after a finite number of steps. At the end, controls the behavior of and for it the result is straightforward. See The remarkable effectiveness of ergodic theory in number theory for further details.
Sixteen years later, in the paper On sets of integers containing no four elements in arithmetic progression, Szemerédi extended Roth’s theorem to
Theorem 3 (Szemerédi) If has positive upper density, then it contains an arithmetic progression of length .
Finally, in , Szemerédi settled the conjecture in its full generality.
Theorem 4 (Szemerédi) If has positive upper density, then it contains arbitrarily long arithmetic progression.
His proof required a complicated combinatorial argument and relied on a graph-theoretical result, known as Szemerédi’s regularity lemma, which turned out to be an important result in graph theory. It asserts, roughly speaking, that any graph can be decomposed into a relatively small number of disjoint subgraphs, most of which behave pseudo-randomly. This is the main topic of this post.
It is worth to mention Erdös also conjectured that if satisfies
then it contains arbitrarily long arithmetic progressions. This question is wide open: nobody knows even if contains arithmetic progressions of length . On the other hand, a remarkable result of Green and Tao states the conjecture for the particular case of the prime numbers.
Theorem 5 (Green and Tao) The prime numbers contain arbitrarily long arithmetic progressions.
2. Setting notation
is a graph, where is a finite set of vertices and is the set of edges, each of them joining two distinct elements of . For disjoint , is the number of edges between and and
is the density of the pair .
Definition 6 For and disjoint subsets , the pair is -regular if, for every and satisfying
A partition of into pairwise disjoint sets in which is called the exceptional set is an equipartition if . We view the exceptional set as distinct parts, each consisting of a single vertex, and its role is purely technical: to make all other classes have exactly the same cardinality.
Definition 7 An equipartition is -regular if
- all but at most of the pairs are -regular.
The classes are called clusters or groups. Given two partitions of , we say refines if every cluster of is equal to the union of some clusters of .
3. Szemerédi’s regularity lemma
Szemerédi’s regularity lemma says that every graph with many vertices can be partitioned into a small number of clusters with the same cardinality, most of the pairs being -regular, and a few leftover edges. In my point of view, this result allows the decomposition of every graph with a sufficiently large number of vertices into many components uniformly (every component has the same number of vertices) in such a way the relation of the clusters is at the same time
uniform: the densities do not vary too much, and
randomic: even controlling the density, nothing can be said about the distribution of the edges.
As a toy model, let and consider the complete random graph with vertices in which every edge belongs to with probability . If are disjoint subsets of , the expected value of is , and the same happens for subsets , . Szemerédi’s regularity lemma says that, approximately, this is indeed the universal behavior.
Note the importance of having an upper bound for the number of clusters. Otherwise, we could just take each of them to be a singleton.
The idea in the proof is similar to Roth’s approach. Start with an arbitrary partition of into disjoint classes of equal sizes. Proceed by showing that, as long as the partition is not -regular, it can be refined in a way to distribute the density deviation. This is done by introducing a bounded energy function that increases a fixed amount every time the refinement is made. After a finite number of steps, the resulting partition is -regular.
We now discuss what should be the energy function. The natural way of looking for it is to identify the obstruction for a pair to be -regular. This means there are subsets and such that , and
Consider the partitions and . The above inequality has the following probabilistic interpretation. Consider the random variable defined on the product by: let be a uniformly random element of and a uniformly random element of , let and be those members of the respective partitions for which and , and take
The expectation of is equal to
By assumption, deviates from at least whenever , and this event has probability
Then . Noting that the expectation of is
we conclude that
The fractions containing above represent the energy function we are looking for: given two disjoint subsets , define
For partitions , let
Definition 9 Given a partition of with exceptional set , the index of is
where the sum ranges over all unordered pairs of distinct parts of , with each vertex of forming a singleton part in its own.
Note that is a sum of terms of the form . The first good property it must have is boundedness.
Property 1. .
In fact, as ,
It is also monotone increasing with respect to refinements. This is the content of the next two properties.
Property 2. If are subsets of and are partitions of , respectively, then
This property follows easily from Cauchy-Schwarz inequality (the interested reader may check it in the survey Szemerédi’s regularity lemma and its applications in graph theory), but this analytical argument is not so clear. A soft way of proving it is to consider the probabilistic point of view, with the aid of the random variable . According to the above calculations,
and so, by Jensen’s inequality (which in this case is just Cauchy-Schwarz inequality),
Property 3. If refines , then
This is a direct consequence of Property 2 by breaking according to :
The next property grows the index of non -regular partitions and reflects the right choice of the energy function. In a few words, it says that
“The lack of uniformity implies energy increment”
and this idea permeates many results in recent developments in combinatorics, harmonic analysis, ergodic theory and others areas. Actually, all known proofs of Szemerédi’s theorem use this principle at some stage. To mention some of them:
- the original proof of Roth considers good and bad parts of functions.
- Furstenberg’s approach: every non-compact system has a weak mixing factor.
- the Fourier-analytic proof of Gowers identifies arithmetic progressions via the nowadays called Gowers norms.
- the construction of characteristic factors for multiple ergodic averages uses the Gowers-Host-Kra seminorms.
These two last results are still being developed to generate what is being called higher-order Fourier analysis. See this post of Terence Tao for a discussion about this topic. Going back to what matters, let’s prove the
Proof: The reader must convince himself that this is exactly relation (3). For those still not convinced, let’s do it again. Assume and are such that , and
Consider and . The evaluation of the variation will prove the proposition. On one hand, by the calculations in Property 2,
On the other, deviates from at least whenever , and this event has probability
Then which, together with (1), gives that
Proposition 11 (Lack of uniformity implies energy increment 2) Suppose and let be a non -regular equipartition of , where is the exceptional set. Then there exists a refinement of with the following properties:
- is an equipartition of ,
Proof: The idea is to apply the previous proposition to every non-regular pair. As there are at least of them, the index will increase the fixed amount. Let be the cardinality of every , . Saying that is not -regular means that, for at least pairs , , is not -regular. For each of these, let , be the partitions of , respectively, given by Proposition 10 and consider the smallest partition that refines and all , . By Proposition 10,
as . This proves that (and any of its refinements) satisfies (iv). The problem is that is not necessarily an equipartition. We adjust this by defining , splitting every part of arbitrarily into disjoint sets of size and throwing the remaining vertices of each part, if any, to the exceptional set. This new partition satisfies (i), (ii) and (iii), as we’ll verify below.
(i) is an equipartition by definition.
(ii) To get , every cluster of is divided in at most parts. After, every element of is divided in at most non-exceptional parts. This implies that
(iii) Each cluster of contributes with at most vertices to and so
Finally, we are able to prove the regularity lemma.
Proof: First, note that if the result is true for and , , then the result is also true for the pair . This allows us to assume that and is arbitrarily large.
Begin with an arbitrary partition of such that and . Apply Proposition 11 at most times to obtain an equipartition . Let be the largest number obtained by iterating the map at most times, starting from . Then has at most clusters. In addition, the cardinality of its exceptional set is bounded by
which is smaller than if is large. This concludes the proof.
There is a large literature about Szemerédi’s regularity lemma. We refer the reader to four references: my lecture notes available at my homepage, the book The probabilistic method of Alon and Spencer, the survey of Komlós and M. Simonovits and Tao’s perspective via random partitions. Merry Christmas!!