Szemerédi Regularity lemma and applications
This block is devoted to a very powerful tool, called Szemerédi Regularity Lemma. Roughly speaking, it states that all dense graphs can be partitioned in finitely many blocks, such that the edges between most of the pairs of blocks behave in a way similar to random bipartite graphs.
Summary: We state and prove the Regularity Lemma, give important companion results: Counting lemma, Removal lemma, Embedding Lemma, and also illustrate its efficiency on some applications. These include Roth's theorem on arithmetic progressions and the Erdős-Stone theorem concerning Turan numbers of graphs with chromatic number at least $3$.
Prerequisites: Basic extremal graph theory
Contents:
Glossary and informal statements ꜜꜛ
For two disjoint sets of vertices $X,Y$ in a graph $G=(V,E)$ we denote $d(X,Y)$ the density of edges between these two sets: $d(X,Y) = \frac {|X||Y|}{|E(X,Y)|}$, where $E(X,Y)$ is the set of edges from $G$ that go between vertices of $X$ and $Y$. The following definition captures the 'quasirandomness' in our setting: for $\epsilon>0$ we say that a pair $X,Y$ is $\epsilon$-regular if for any $A\subset X, B\subset Y$ such that $|A|\ge \epsilon|X|, |B|\ge \epsilon|Y|$ we have $|d(A,B)-d(X,Y)|\le \epsilon$. In words, the density of edges between any two large subsets of $X,Y$ is roughly the same as the density of edges between $X$ and $Y$. Note that this definition makes sense only in the case there $E(X,Y)$ is large w.r.t. $|X||Y|$ (somewhat informally, "the graph is dense"): roughly speaking, $d(X,Y)$ should be at least $\epsilon$.
Regularity Lemma: For any $\epsilon>0$ any graph can be split in $M(\epsilon)$ parts $V_1,\ldots, V_M$ such that most pairs $V_i,V_j$ are $\epsilon$-regular. (Crucially, $M$ is independent of the number of vertices of the graph.)
There are differences between statements of the Regularity lemma. In some videos we have a "trash" part $V_0$ in the partition, in some we only have the "normal" parts. In some cases parts have equal (or nearly equal) size, in some they don't. We note that the statements are equivalent, and it is not difficult to pass from one to another. In the applications, it is usually easier to work with parts of equal size.
For a partition, we can define the reduced graph $R$ by representing each part as a vertex and connecting two parts $V_i,V_j$ if this pair is $\epsilon$-regular and reasonably dense.
For $H$, a $t$-blow-up of $H$ is a graph obtained from $H$ by replacing each vertex by a group of $t$ vertices and each edge by a complete bipartite graph $K_{t,t}$.
The name of the next lemma is non-standard, but it is helpful to distinguish it from the 'real' blow-up lemma. It is the easiest application of the Regularity Lemma, and is already very powerful.
Constant Blow-Up Lemma: If $R$ is the reduced graph of $G$ and $R$ contains a graph $H$ then $G$ contains a $t$-blow-up of $H$ for `reasonable' constant $t$.
And other results:
Counting Lemma: If $R$ is the reduced graph of $G$ and $R$ contains a graph $H$ then $G$ contains a lot of copies of $H$ (i.e., a linear proportion of all possible copies of $H$ on the same set of vertices).
Removal Lemma: If $G$ contains few copies of $H$, then $G$ can be made $H$-free by removing few edges.
Embedding Lemma: If $R$ is the reduced graph of $G$ and a $t$-blow-up of $R$ contains a bounded-degree graph $H$, then $G$ contains a $H$, provided the maximum degree of $H$ is constant and $t$ is somewhat small with respect to $V(G)$ (it's at most a small constant fraction of $|V(G)|$). It also has a counting version.
Blow-up Lemma: It is the same as the Embedding Lemma, except, roughly speaking, $H$ now can be a spanning subgraph. More precisely, if $H$ has constant max degree and it can be embedded into a $t$-blow-up of some graph $W$, then $H$ can also be embedded into a graph $G$, that is obtained from $W$ by replacing each vertex $i$ with a set $V_i$ of $t$ vertices and making each pair $V_i,V_j$ that corresponds to an edge of $W$ and $\epsilon$-regular pair.
Set 1
One that maybe the most intuitive is to start with what is called a Blow-Up lemma and to show how one can use $\epsilon$-regular pairs, and only then go to Regularity Lemma. This original approach is proposed by Po-Shen Loh in his great graduate combinatorics course. The set of videos is overall much longer than the others, but gives a clear and intuitive explanation. Here is the video in which he deduces the Constant Blow-Up Lemma:
Here is the next video, in which he introduces the statement of Szemerédi's Regularity lemma and then applies it to get the Erdős-Stone theorem that states that $ex(n,H) = (1-\frac 1r+o(1)){n\choose 2}$ for any graph $H$ with chromatic number $r+1\ge 3$.
In the next two lectures he proves the Regularity lemma:
Set 2
This sequence of video lectures is taken from a course by Yufei Zhao. This is the sequence I would probably recommend. The lectures have an intermediate speed. All proofs are very cleanly explained. As a great addition, it gives some applications of the proofs to additive combinatorics. In the following video, he gives a proof of the Regularity Lemma.
In the next video, he proves the triangle counting and triangle removal lemma, and gives an important application to additive combinatorics: he proves Roth theorem that states that any subset of $[n]$ without an 3-term arithmetic progression has $o(n)$ points.
In the next lecture he introduces tools that generalize triangle counting / removal lemmas: he states graph embedding lemma (without a proof), and proves a graph counting lemma using a rather non-standard and very elegant approach that is based on embedding edges, rather than vertices, states graph removal lemma, and gives a proof of the Erdős-Stone theorem (via graph removal lemma, rather than Constant Blow-Up lemma).
Set 3
These are two quick and rather dense videos from the course of Luke Postle. In the first video he presents the proof (or rather, a detailed sketch that omits calculations) of the Regularity Lemma.
In the next video, he proves the Embedding Lemma (which he calls the Blow-Up lemma) and deduces the Erdős-Stone theorem.
Applications ꜜꜛ
We have mentioned some applications above, here we repeat them. First, it is the Erdős-Stone theorem that states that $ex(n,H) = (1-\frac 1r+o(1)){n\choose 2}$ for any graph $H$ with chromatic number $r+1\ge 3$.
Here is a proof via Constant Blow-Up Lemma :
Here is a proof via Graph Removal Lemma :
Here is an application to Ramsey theory from a lecture by Luke, which implies that for any graph $H$ with maximum degree $\Delta$ there is a number $r\le C(\Delta) |V(H)|$ such that in any two-coloring of $K_r$ into two colors we can a monochromatic copy of $H$. Importantly, the dependence on the number of vertices of $H$ is linear . Before that a recap on Ramsey numbers and a lower bound construction for Ramsey number of a complete graph:
Here are the applications to additive combinatorics by Yufei: Roth's theorem that states that any subset of $[n]$ without an 3-term arithmetic progression has $o(n)$ points , starting from a certain graph theory statement about a graph in which each edge is contained in exactly $1$ triangle]:
In the next Yufei's lecture, there is a lower bound construction for Roth's theorem and an upper-bound result of a similar spirit for corners: any corner-free set in $[n]\times [n]$ has $o(n^2)$ points :
Advanced topics ꜜꜛ
In the continuation of his course, Yufei Zhao tells about an induced graph removal lemma, that informally states the following: if a graph $G$ has few induced copies of some graph $H$, then the graph $G$ can be made induced $H$-free by adding or deleting few edges. To do so, he introduces what is known as a strong regularity lemma, which, as a corollary, allows to find large subsets $W_i$ in each part of a partition $V_i$ such that every pair $(W_i,W_j)$ is $\epsilon$-regular (including pairs $(W_i,W_i)$) and the density $d(W_i,W_j)$ is close to $d(V_i,V_j)$ for most pairs. Note that, in this setting, there is no exceptional set either. He then shows a (computer science) application to property testing: an efficient way to verify if a graph is close to, say, being triangle free.
Recall that a $t$-uniform hypergraph is a pair $(V,E)$, where $V$ is a set of vertices and $E$ is a collection of $t$-element subsets of $V$. In the next video, Yufei speaks about the form of the hypergraph regularity lemma (for 3-uniform hypergraphs) and different obstracles that may arise on the way. He also relates this to Szemerédi's theorem about arithmetic progressions in dense sets. In the last part , he sketches a different proof of the regularity lemma, based on a spectral decomposition of real symmetric matrices.
In the next video, Yufei speaks about regularity and counting for sparse graphs. One of the main takeaways is that, in order for the same paradigm to work, we need to consider sufficiently dense subgraphs of sufficiently quasirandom graphs, where the notion of quasirandomness is one of the most important points. He relates it to the Green-Tao theorem about arbitrarily long arithmetic progressions in primes.
Further reading ꜜꜛ
For more details and applications, I recommend the following survey on regularity: The Regularity Lemma and Its Applications in Graph Theory by János Komlós, Ali Shokoufandeh, Miklós Simonovits and Endre Szemerédi.