Szemerédi regularity lemma

Statement

Definition 1. Let be disjoint subsets of. The edge density of the pair is defined as:
where denotes the set of edges having one end vertex in and one in.

Definition 2. For, a pair of vertex sets and is called -regular, if for all subsets, satisfying,, we have
The natural way to define an -regular partition should be one where each pair of parts is -regular. However, some graphs, such as the half graphs, require many pairs of partitions to be irregular. So we shall define -regular partitions to be one where most pairs of parts are -regular.

Definition 3. A partition of into sets is called an -regular partition if

Now we can state the lemma:

Szemerédi's regularity Lemma. For every and positive integer there exists an integer such that if is a graph with at least vertices, there exists an integer in the range and an -regular partition of the vertex set of into sets.

The bound for the number of parts in the partition of the graph given by the proofs of Szemeredi's regularity lemma is very large, given by a -level iterated exponential of. At one time it was hoped that the true bound was much smaller, which would have had several useful applications. However found examples of graphs for which does indeed grow very fast and is at least as large as a -level iterated exponential of.

Proof

We shall find an ε-regular partition for a given graph following an algorithm:

1. Start with a partition
2. While the partition isn't ε-regular:
3. *Find the subsets which witness ε-irregularity for each irregular pair.
4. Refine the partition using all the witnessing subsets.

We apply a technique called the energy increment argument to show that this process stops after a bounded number of steps. To do this, we define a measure which must increase by a certain amount in each step, but it's bounded above and thus cannot increase indefinitely. This measure is called 'energy' as it's an quantity.

Definition 4. Let be subsets of. Set. The energy of the pair is defined as:
For partitions of and of, we define the energy to be the sum of the energies between each pair of parts:
Finally, for a partition of, define the energy of to be. Specifically,

Note that energy is between 0 and 1 because edge density is bounded above by 1:
Now, we start by proving that energy does not decrease upon refinement.

Lemma 1. For any partitions and of vertex sets and,.

Proof: Let and. Choose vertices uniformly from and uniformly from, with in part and in part. Then define the random variable. Let us look at properties of. The expectation is
The second moment is
By convexity,. Rearranging, we get that for all.

If each part of is further partitioned, the new partition is called a refinement of. Now, if, applying Lemma 1 to each pair proves that for every refinement of,. Thus the refinement step in the algorithm doesn't lose any energy.

Lemma 2. If is not -regular as witnessed by, then,

Proof: Define as above. Then,
But observe that with probability, so

Now we can prove the energy increment argument, which shows that energy increases substantially in each iteration of the algorithm.

Lemma 3 If a partition of is not -regular, then there exists a refinement of where every is partitioned into at most parts such that

Proof: For all such that is not -regular, find and that witness irregularity. Let be a common refinement of by 's. Each is partitioned into at most parts as desired. Then,
Where is the partition of given by. By Lemma 1, the above quantity is at least
Since is cut by when creating, so is a refinement of. By lemma 2, the above sum is at least
But the second sum is at least since is not -regular, so we deduce the desired inequality.

Now, starting from any partition, we can keep applying Lemma 3 as long as the resulting partition isn't -regular. But in each step energy increases by, and it's bounded above by 1. Then this process can be repeated at most times, before it terminates and we must have an -regular partition.

Applications

Graph counting lemma

If we have enough information about the regularity of a graph, we can count the number of copies of a specific subgraph within the graph up to small error.

Graph Counting Lemma. Let be a graph with, and let. Let be an -vertex graph with vertex sets such that is -regular whenever. Then, the number of labeled copies of in is within of
This can be combined with Szemerédi's regularity lemma to prove the Graph removal lemma. The graph removal lemma can be used to prove Roth's Theorem on Arithmetic Progressions, and a generalization of it, the hypergraph removal lemma, can be used to prove Szemerédi's theorem.
The graph removal lemma generalizes to induced subgraphs, by considering edge edits instead of only edge deletions. This was proved by Alon, Fischer, Krivelevich, and Szegedy in 2000. However, this required a stronger variation of the regularity lemma.
Szemerédi's regularity lemma does not provide meaningful results in sparse graphs. Since sparse graphs have subconstant edge densities, -regularity is trivially satisfied. Even though the result seems purely theoretical, some attempts have been made to use the regularity method as compression technique for large graphs.

Frieze-Kannan regularity

A different notion of regularity was introduced by Frieze and Kannan, known as the weak regularity lemma. This lemma defines a weaker notion of regularity than that of Szemerédi which uses better bounds and can be used in efficient algorithms.
Given a graph, a partition of its vertices is said to be Frieze-Kannan -regular if for any pair of sets :
The weak regularity lemma for graphs states that every graph has a weak -regular partition into at most parts.
This notion can be extended to graphons by defining a stepping operator. Given a graphon and a partition of, we can define as a step-graphon with steps given by and values given by averaging over each step.
A partition is weak -regular if:
The weak regularity lemma for graphons states that every graphon has a weak -regular partition into at most parts. As with Szemerédi's regularity lemma, the weak regularity also induces a counting lemma.

Algorithmic applications

One of the initial motivations for the development of the weak regularity lemma was the search for an efficient algorithm for estimating the maximum cut in a dense graph. It has been shown that approximating the max-cut problem beyond 16/17 is NP-hard, however an algorithmic version of the weak regularity lemma gives an efficient algorithm for approximating the max-cut for dense graphs within an additive error. These ideas have been further developed into efficient sampling algorithms for estimating max-cut in dense graphs.
The smaller bounds of the weak regularity lemma allow for efficient algorithms to find an -regular partition. Graph regularity has further been used in various area of theoretical computer science, such as matrix multiplication and communication complexity.

Strong regularity lemma

The strong regularity lemma is a stronger variation of the regularity lemma proven by Alon, Fischer, Krivelevich, and Szegedy in 2000. Intuitively, it provides information between non-regular pairs and could be applied to prove the induced graph removal lemma.

Statement

For any infinite sequence of constants, there exists an integer such that for any graph, we can obtain two partitions and such that the following properties are satisfied:

• refines, that is every part of is the union of some collection of parts in.
• is -regular and is -regular.

• Proof

We apply the regularity lemma repeatedly to prove the stronger version. A rough outline:

• Start with be an regular partition
• Repeatedly find its refinement that is regular. If the energy increment of, we simply return. Otherwise, we replace with and continue.

We start with be an regular partition of with parts. Here corresponds to the bound of parts in regularity lemma when.
Now for, we set to be an regular refinement of with parts. By the energy increment argument,. Since the energy is bounded in, there must be some such that. We return as.
By our choice of the regular and refinement conditions hold. The energy condition holds trivially. Now we argue for the number of parts. We use induction to show that, there exists such that. By setting, we have. Note that when,, so we could set and the statement is true for. By setting, we have