May | 2020 | Trying to be a mathematician

I have taken an interest in regularity lemmas recently, starting with the weak regularity lemma of Frieze and Kannan (in order to understand Szemerédi’s theorem on arithmetic progressions), and decided that I needed to understand the proof of the full regularity lemma. The reference I’m using is Reinhard Diestel‘s book Graph Theory. The regularity lemma seems almost magically powerful to me, and has many applications (and generalisations, but we’ll get to that), but the proof is not all that hard. This post won’t present the full proof, just an overview to get the feel of it. (For another perspective on the regularity lemma by someone who actually knows what he is doing, see Yufei Zhao’s blog entry https://yufeizhao.wordpress.com/2012/09/07/graph-regularity/.)

Much like certain proofs of Roth’s theorem, the idea behind the proof of the regularity lemma is to increase a bounded positive quantity by a constant in each iteration. There are only so many times you can do this, and when you stop, what is left must satisfy the conditions of the lemma. Firstly, some definitions.

Definition 1. Let $G=(V,E)$ be a graph. We say that a pair of disjoint subsets $U,W \subset V$ is $\varepsilon$ -regular if

$|d(U,W) - d(U_1 ,W_1)| < \varepsilon$

for any subsets $U_1 \subseteq U$ and $W_1 \subseteq W$ for which $|U_1 |\geq \varepsilon |U|$ and $|W_1 |\geq \varepsilon |W|$ .

In the above, $d(U,W)$ as usual denotes edge density

$\frac{\| U,V\|}{|U||W|}$

between $U$ and $W$ .

Definition. Let $\varepsilon >0$ be given and let $G=(V,E)$ , $|V|=n$ , be a graph. We say that a partition $\{ V_0 ,V_1 , \dots V_k \}$ of the vertices of the graph is $\varepsilon$ -regular if

$|V_0| \leq \varepsilon n$
$|V_1| = |V_2| = \cdots =|V_k|$
Each pair $(V_i ,V_j)$ , $i\neq j$ is $\varepsilon$ -regular for all but at most $\varepsilon k^2$ of the possible pairs.

The regularity lemma (in one form; there are several equivalent ones) can be stated as follows.

Regularity Lemma. Give some $\varepsilon >0$ and some $m\geq 1$ , there exists an integer $M$ such that any graph $G = (V,E)$ of order at least $m$ admits an $\varepsilon$ -regular partition $\{ V_0 , V_1 , \dots ,V_k \}$ where $m\leq k \leq M$ .

The quantity that we will bound is a kind of $L^2$ norm on the graph. If $A,B \subseteq V$ and disjoint, set

$q(A,B) = \frac{|A| |B|}{n^2}d(A,B)^2 = \frac{\| A,B \|^2}{|A||B|n^2},$

where $n = |V|$ . It should be clear that $q(A,B) \leq 1$ . In effect, we consider $A\cup B$ as a bipartite graph. If the graph is complete, $q$ will be $|A||B|/(|A| +|B|)^2 <1/2$ , and $0$ when empty. It does not seem to me that the quantity has a very intuitive meaning. However, it does satisfy the conditions of being bounded and increasing under successive partitions, which is what we’ll need. Suppose that $\mathcal{C}$ is a partition of $C$ and $\mathcal{D}$ is a partition of $D$ . We define

$q(\mathcal{C} , \mathcal{D} ) = \sum_{A \in \mathcal{C}, B \in \mathcal{D}} q(A,B)$ .

The fundamental fact which we can prove (quite easily) is that, with all objects as above,

$q(\mathcal{C},\mathcal{D}) \geq q(C,D).$

If we have a partition $\mathcal{P} = \{V_1 , \dots ,V_k \}$ of the graph $G$ , we define

$q(\mathcal{P}) = \sum_{i\neq j} q(V_j ,V_j).$

We can now prove from the above that if $\mathcal{P}'$ is a refinement of the partition $\mathcal{P}$ , then

$q(\mathcal{P}') \geq \mathcal{P}.$

We can already start to spy the strategy of the proof here – we have a bounded quantity that increases with further partitions. What we have to prove is that such refinement of partitions will increase by a fixed amount, which means that it can be done only a bounded number of times, given that $q$ is bounded by $1$ .

Suppose we are now given a partition of $V$ , namely $\{ V_0 ,V_1 , \dots ,V_k \}$ , where all the members except $V_0$ have the same size. We regard $V_0$ as a set of members of the partition itself, each a singleton. We set

$\mathcal{P} = \{ V_1, \dots , V_k \} \cup \{ \{ v \} : v\in V_0 \}$

and define the quantity $q$ for our partition ${ V_0 ,V_1 , \dots ,V_k }$ as $q(\mathcal{P} )$ . With our definitions in place, we can start assembling the required lemmas.

Lemma 0. From the Cauchy-Schwarz inequality, we can conclude that

$\sum \frac{e_{i}^{2} }{\mu_i} \geq \frac{(\sum e_i )^2}{\sum \mu_i}.$

We won’t be using this lemma in this post (hence calling it Lemma 0), but it is essential in working out the details of the following lemmas.

Lemma 1. If $C,D \subset V$ are disjoint and not $\varepsilon$ -regular, there are partitions $\mathcal{C} = \{ C_1 ,C_2 \}$ of $C$ and $\mathcal{D} = \{ D_1 , D_2 \}$ of $D$ such that

$q(\mathcal{C} , \mathcal{D} ) \geq q(C,D) + \frac{\varepsilon^4 }{|C| |D| n^2}.$

For the proof, we pick the sets $C_1$ and $D_1$ to be two sets of sizes no less than $\varepsilon |C|$ and $\varepsilon |D|$ , respectively, witnessing the irregularity of $(C,D)$ , and $C_2$ and $D_2$ to be what is left over in $C$ and $D$ .

Using Lemma 1, we can prove the following crucial lemma.

Lemma 2. Let $\varepsilon$ be such that $0<\varepsilon \leq 1/4$ . If $\mathcal{P} = \{ V_0 ,V_1, \dots ,V_k \}$ is an $\varepsilon$ -irregular partition of $V$ where $|V_1 | = |V_2 | = \cdots = |V_k |$ and $|V_0| \leq \varepsilon n$ , then there is a partition $\mathcal{P}' = \{ W_0 , W_1 , \dots ,W_l \}$ , $k\leq l \leq k4^k$ , of $V$ such that $|W_1| = |W_2 | = \cdots = |W_l |$ and $|W_0 | \leq |V_0 | + n/2^k$ such that

$q( \mathcal{P} ' ) \geq q( \mathcal{P} ) + \frac{ \varepsilon^5 }{2}.$

The crucial part here is that the constant increased by does not depend on any of the parameters except $\varepsilon$ . The idea behind the proof of Lemma 2 is to compare all pairs of sets $V_i , V_j$ in the first partition, that might be irregular, then use Lemma 1 to partition them. We take a common refinement of all of these partitions, then partition further to obtain sets of equal cardinality, shunting all the vertices left over into $V_0$ .

What astounds me about Lemma 2 is how wasteful it seems to be. We just partition according to Lemma 1 until we get the desired refinement, and yet this is still powerful enough to lead directly to the result we’re after.

We can now carefully pick our constants and iterate Lemma 2 until we obtain the regularity lemma. Pick $\varepsilon$ such that $0< \varepsilon \leq 1/4$ . We will need to determine the constants $m$ and $M$ , depending on $\varepsilon$ but not on $G$ . These depend on how many times we have to implement Lemma 2, and how many further partitions each use of Lemma 2 creates. Because the $q$ -value of a partition cannot be greater than $1$ , we know that the number of iterations has to be bounded by $s = 2/ \varepsilon^5$ . Now, at each stage the cardinality of the exceptional set may increase by $n/2^k$ , if we start with a partition $\{ C_0 , C_1 , \dots ,C_k \}$ . We want to prevent the size of the exceptional set at any stage from exceeding $\varepsilon n$ , and since we start with some $C_0$ with $|C_0 |\leq \frac{1}{2} \varepsilon n$ , we have to make sure that $s$ iterations of adding $n/2^k$ do not exceed $\frac{1}{2}\varepsilon n$ either. (This is not precise, since the exceptional set will not actually increase by the same factor at each stage, but this will certainly do.) Now $n$ must be chosen large enough so that for the initial exceptional set $C_0$ , we have a large $k$ so that $|C_0| < k$ and $|C_0 |\leq \frac{1}{2} \varepsilon n$ . The exceptional set should be allowed up to $k$ members, to ensure we have equal cardinality for all the other sets. If $k\geq m$ is large enough to allow $2^{k-1} \geq s/\varepsilon$ , we have $s/2^k \leq \varepsilon /2$ and

$k+\frac{s}{2^k} n \leq \varepsilon n$

for $n\geq 2k/ \varepsilon$ .

What is left is to choose $M$ . We choose $M$ larger than the maximum of $2k/\varepsilon$ and the number of sets (non-exceptional) that can be generated by $s$ applications of the previous lemma, that is, $s$ iterations of $r$ elements of the partition increasing to $r4^r$ elements.

As long as our graph is relatively small, it is easy to show that a suitable partition exists. If the graph has order $n$ , where $m\leq n \leq M$ , we choose $V_0 = \emptyset$ and let $|V_1| = |V_2| = \cdots = |V_n|$ . For $n> M$ , we want to start with a partition which satisfies $|W_0| \leq \frac{1}{2} \varepsilon n$ for Lemma 2 to be valid. Let $k$ be as we established above. Now, let $W_0$ be a minimal subset of $V$ so that $k$ divides $V\setminus W_0$ . We then partition $V\setminus W_0$ into $k$ sets of equal cardinality. Because $k\leq \frac{1}{2} \varepsilon n$ , Lemma 2 is applicable, and we simply apply it repeatedly to obtain the partition we are after.