4Szemeredi's regularity lemma
III Extremal Graph Theory
4 Szemer´edi’s regularity lemma
Szmer´edi’s regularity lemma tells us given a very large graph, we can always
equipartition it into pieces that are “uniform” in some sense. The lemma is
arguably “trivial”, but it also has many interesting consequences. To state the
lemma, we need to know what we mean by “uniform”.
Definition
(Density)
.
Let
U, W
be disjoint subsets of the vertex set of some
graph. The number of edges between
U
and
W
is denoted by
e
(
U, W
), and the
density is
d(U, W ) =
e(U, W )
|U||W |
.
Definition
(
ε
-uniform pair)
.
Let 0
< ε <
1. We say a pair (
U, W
) is
ε
-uniform
if
|d(U
0
, W
0
) − d(U, W )| < ε
whenever U
0
⊆ U, W
0
⊆ W , and |U
0
| ≥ ε|U|, |W
0
| ≥ ε|W |.
Note that it is necessary to impose some conditions on how small
U
0
and
W
0
can be. For example, if
|U
0
|
=
|W
0
|
= 1, then
d
(
U
0
, W
0
) is either 0 or 1. So we
cannot have a sensible definition if we want to require the inequality to hold for
arbitrary U
0
, W
0
.
But we might be worried that it is unnatural to use the same
ε
for two
different purposes. This is not something one should worry about. The Szemer´edi
regularity lemma is a fairly robust result, and everything goes through if we use
different
ε
’s for the two different purposes. However, it is annoying to have to
have many different ε’s floating around.
Before we state and prove Szemer´edi’s regularity lemma, let’s first try to
understand why uniformity is good. The following is an elementary observation.
Lemma. Let (U, W ) be an ε-uniform pair with d(U, W ) = d. Then
|{u ∈ U : |Γ(u) ∩ W | > (d − ε)|W |}| ≥ (1 − ε)|U |
|{u ∈ U : |Γ(u) ∩ W | < (d + ε)|W |}| ≥ (1 − ε)|U |,
where Γ(u) is the set of neighbours of u.
Proof. Let
X = {u ∈ U : |Γ(u) ∩ W | ≤ (d − ε)|W |}.
Then e(X, W ) ≤ (d − ε)|X||W |. So
d(X, W ) ≤ d − ε = d(U, W ) − ε.
So it fails the uniformity condition. Since
W
is definitely not small, we must
have |X| < ε|U|.
The other case is similar, or observe that the complementary bipartite graph
between U and W has density 1 −d and is ε-uniform.
What is good about
ε
-uniform pairs is that if we have enough of them, then
we can construct essentially any subgraph we like. Later, Szemer´edi’s regularity
lemma says any graph large enough has
ε
-uniform equipartitions, and together,
they can give us some pretty neat results.
Lemma
(Graph building lemma)
.
Let
G
be a graph containing distinct vertex
subsets
V
1
, . . . , V
r
with
|V
i
|
=
u
, such that (
V
i
, V
j
) is
ε
-uniform and
d
(
V
i
, V
j
)
≥ λ
for all 1 ≤ i ≤ j ≤ r.
Let
H
be a graph with maximum degree ∆(
H
)
≤
∆. Suppose
H
has an
r
-colouring in which no colour is used more than
s
times, i.e.
H ⊆ K
r
(
s
), and
suppose (∆ + 1)ε ≤ λ
∆
and s ≤ bεuc. Then H ⊆ G.
To prove this, we just do what we did in the previous lemma, and find lots
of vertices connected to lots of other vertices, and then we are done.
Proof.
We wlog assume
V
(
H
) =
{
1
, . . . , k}
, and let
c
:
V
(
H
)
→ {
1
, . . . , r}
be a
colouring of
V
(
H
) using no colour more than
s
times. We want to pick vertices
x
1
, . . . , x
k
in G so that x
i
x
j
∈ E(G) if ij ∈ E(H).
We claim that, for 0
≤ ` ≤ k
, we can choose distinct vertices
x
1
, . . . , x
`
so
that x
j
∈ C
c(j)
, and for ` < j ≤ k, a set X
`
j
of candidates for x
j
such that
(i) X
`
j
⊆ V
c(j)
;
(ii) x
i
y
j
∈ E(G) for all y
j
∈ X
`
j
and i ≤ ` such that ij ∈ E(H).
(iii) |X
`
j
| ≥ (λ − ε)
|N(j,`)|
|V
c(j)
|, where
N(j, `) = {x
i
: 1 ≤ i ≤ ` and ij ∈ E(H)}.
The claim holds for ` = 0 by taking X
0
j
= V
c(j)
.
By induction, suppose it holds for
`
. To pick
x
`+1
, of course we should pick it
from our candidate set
X
`
`+1
. Then the first condition is automatically satisfied.
Define the set
T = {j > ` + 1 : (` + 1)j ∈ E(H)}.
Then each
t ∈ T
presents an obstruction to (ii) and (iii) being satisfied. To
satisfy (ii), for each t ∈ T , we should set
X
`+1
t
= X
`
t
∩ Γ(x
`+1
).
Thus, to satisfy (iii), we want to exclude those
x
`+1
that make this set too small.
We define
Y
t
=
n
y ∈ X
`
`+1
: |Γ(y) ∩ X
`
t
| ≤ (λ − ε)|X
`
t
|
o
.
So we want to find something in
X
`
`+1
\
S
t∈T
Y
t
. We also cannot choose one of
the x
i
already used. So our goal is to show that
X
`
`+1
−
[
t∈T
Y
t
> s − 1.
This will follow simply from counting the sizes of
|X
`
`+1
|
and
|Y
t
|
. We already
have a bound on the size of
|X
`
`+1
|
, and we shall show that if
|Y
t
|
is too large,
then it violates ε-uniformity.
Indeed, by definition of Y
t
, we have
d(Y
t
, X
`
`+1
) ≤ λ − ε ≤ d(V
c(t)
, V
c(`+1)
) − ε.
So either |X
`
`+1
| < ε|V
c(t)
| or |Y
t
| < ε|V
c(`+1)
|. But the first cannot occur.
Indeed, write
m
=
|N
(
`
+ 1
, `
)
|
. Then
m
+
|T | ≤
∆. In particular, since the
|T | = 0 case is trivial, we may assume m ≤ ∆ − 1. So we can easily bound
|X
`+1
| ≥ (λ − ε)
∆−1
|V
c(t)
| ≥ (λ
∆−1
− (∆ − 1)ε)|V
c(t)
| > ε|V
c(t)
|.
Thus, by ε-uniformity, it must be the case that
|Y
t
| ≤ ε|V
c(`+1)
|.
Therefore, we can bound
X
`
`+1
−
[
t∈T
Y
t
≥ (λ − ε)
m
|V
c(`+1)
| − (∆ − m)ε|V
c(`+1)
|
≥ (λ
m
− mε − (∆ − m)ε)u ≥ εu > s − 1.
So we are done.
Corollary.
Let
H
be a graph with vertex set
{v
1
, . . . , v
r
}
. Let 0
< λ, ε <
1
satisfy rε ≤ λ
r−1
.
Let
G
be a graph with disjoint vertex subsets
V
1
, . . . , V
r
, each of size
u ≥
1.
Suppose each pair (
V
i
, V
j
) is
ε
uniform, and
d
(
V
i
, V
j
)
≥ λ
if
v
i
v
j
∈ E
(
H
), and
d
(
V
i
, V
j
)
≤
1
− λ
if
v
i
v
j
6∈ E
(
H
). Then there exists
x
i
∈ V
i
so that the map
v
i
→ x
i
is an isomorphism H → G[{x
1
, . . . , x
r
}].
Proof.
By replacing the
V
i
-
V
j
edges by the complementary set whenever
v
i
v
j
6∈
E(H), we may assume d(V
i
, V
j
) ≥ λ for all i, j, and H is a complete graph.
We then apply the previous lemma with ∆ = r − 1 and s = 1.
Szemer´edi showed that every graph that is sufficiently large can be partitioned
into finitely many classes, with most pairs being
ε
-uniform. The idea is simple
— whenever we see something that is not uniform, we partition it further into
subsets that are more uniform. The “hard part” of the proof is to come up with
a measure of how far we are from being uniform.
Definition
(Equipartition)
.
An equipartition of
V
(
G
) into
k
parts is a partition
into sets V
1
, . . . , V
k
, where b
n
k
c ≤ V
i
≤ d
n
k
e, where n = |G|.
We say that the partition is
ε
-uniform if (
V
i
, V
j
) is
ε
-uniform for all but
ε
k
2
pairs.
Theorem
(Szemer´edi’s regularity lemma)
.
Let 0
< ε <
1 and let
`
be some
natural number. Then there exists some
L
=
L
(
`, ε
) such that every graph has
an
ε
-uniform equipartition into
m
parts for some
` ≤ m ≤ L
, depending on the
graph.
This lemma was proved by Szemer´edi in order to prove his theorem on
arithmetic progressions in dense subsets of integers.
When we want to apply this, we usually want at least
`
many parts. For
example, having 1 part is usually not very helpful. The upper bound on
m
is helpful for us to ensure the parts are large enough, by picking graphs with
sufficiently many vertices.
We first need a couple of trivial lemmas.
Lemma.
Let
U
0
⊆ U
and
W
0
⊆ W
, where
|U
0
| ≥
(1
− δ
)
|U|
and
|W
0
| ≥
(1 − δ)|W |. Then
|d(U
0
, W
0
) − d(U, W )| ≤ 2δ.
Proof. Let d = d(U, W ) and d
0
= d(U
0
, W
0
). Then
d =
e(U, W )
|U||W |
≥
e(U
0
, W
0
)
|U||W |
= d
0
|U
0
||W
0
|
|U||W |
≥ d
0
(1 − δ)
2
.
Thus,
d
0
− d ≤ d
0
(1 − (1 − δ)
2
) ≤ 2δd
0
≤ 2δ.
The other inequality follows from considering the complementary graph, which
tells us
(1 − d
0
) − (1 − d) ≤ 2δ.
Lemma. Let x
1
, . . . , x
n
be real numbers with
X =
1
n
n
X
i=1
x
i
,
and let
x =
1
m
m
X
i=1
x
i
.
Then
1
n
n
X
i=1
x
2
i
≥ X
2
+
m
n − m
(x − X)
2
≥ X
2
+
m
n
(x − X)
2
.
If we ignore the second term on the right, then this is just Cauchy–Schwarz.
Proof. We have
1
n
n
X
i=1
x
2
i
=
1
n
m
X
i=1
x
2
i
+
1
n
n
X
i=m+1
x
2
i
≥
m
n
x
2
+
n − m
n
nX − mx
n − m
2
≥ X
2
+
m
n − m
(x − X)
2
by two applications of Cauchy–Schwarz.
We can now prove Szemer´edi’s regularity lemma.
Proof. Define the index ind(P) of an equipartition P into k parts V
i
to be
ind(P ) =
1
k
2
X
i<j
d
2
(V
i
, V
j
).
We show that if
P
is not
ε
-uniform, then there is a refinement equipartition
Q
into k4
k
parts, with ind(Q) ≥ ind(P) +
ε
5
8
.
This is enough to prove the theorem. For choose
t ≥ `
with 4
t
ε
5
≥
100.
Define recursively a function f by
f(0) = t, f(j + 1) = f(j)4
f(j)
.
Let
N = f(d4ε
−5
e),
and pick L = N 16
N
.
Then, if
n ≤ L
, then just take an equipartition into single vertices. Otherwise,
begin with a partition into
t
parts. As long as the current partition into
k
parts
is not
ε
uniform, replace it a refinement into 4
k
4
parts. The point is that
ind
(
P
)
≤
1
2
for any partition. So we can’t do this more than 4
ε
−5
times, at
which point we have partitioned into N ≤ L parts.
Note that the reason we had to set
L
=
N
16
N
is that in our proof, we want
to assume we have many vertices lying around.
The proof really is just one line, but students tend to complain about such
short proofs, so let’s try to explain it in a bit more detail. If the partition is
not
ε
-uniform, this means we can further partition each part into uneven pieces.
Then our previous lemma tells us this discrepancy allows us to push up
1
n
P
x
2
i
.
So given an equipartition
P
that is not
ε
-uniform, for each non-uniform pair
(V
i
, V
j
) of P , we pick witness sets
X
ij
⊆ V
i
, X
ji
⊆ V
j
with |X
ij
| ≥ ε|V
i
|, |X
ji
| ≥ |V
j
| and |d(X
ij
, X
ji
) − D(V
i
, V
j
)| ≥ ε.
Fix
i
. Then the sets
X
ij
partition
V
i
into at most 2
k−1
atoms. Let
m
=
b
n
k4
k
c
,
and let n = k4
k
m + ak + b, where 0 ≤ a ≤ 4
k
and b ≤ k. Then we see that
bn/kc = 4
k
m + a
and the parts of P have size 4
k
m + a or 4
k
m + a + 1, with b of the larger size.
Partition each part of
P
into 4
k
sets, of size
m
or
m
+ 1. The smaller
V
i
having a parts of size m + 1, and thelargrer having a + 1 such pairs.
We see that any such partition is an equipartition into
k
4
k
parts of size
m
or
m + 1, with ak + b parts of larger size m + 1.
Let’s choose such an equipartition Q with parts as nearly as possible inside
atoms, so each atom is a union of parts of Q with at most m extra vertices.
All that remains is to check that ind(Q) ≥ ind(P) +
ε
5
8
.
Let the sets of Q within V
i
be V
i
(s), where 1 ≤ s ≤ 4
k
≡ q. So
V
i
=
q
[
s=1
V
i
(s).
Now
X
1≤s,t≤q
e(V
i
(s), V
j
(t)) = e(V
i
, V
j
).
We’d like to divide by some numbers and convert these to densities, but this is
where we have to watch out. But this is still quite easy to handle. We have
m
m + 1
≤ q|V
i
(s)| ≤ |V
i
| ≤
m + 1
m
q|V
i
(s)|
for all s. So we want m to be large for this to not hurt us too much.
So
m
m + 1
d(V
i
, V
j
) ≤
1
q
2
X
s,t
d(V
i
(s), V
j
(t)) ≤
m + 1
m
2
d(V
i
, V
j
).
Using n ≥ k16
k
, and hence
m
m + 1
2
≥ 1 −
2
m
≥ 1 −
2
4
k
≥ 1 −
ε
5
50
,
we have
1
q
2
X
s,t
d(V
i
(s), V
j
(t)) − d(V
i
, V
j
)
≤
ε
5
49
+ d(V
i
, V
j
).
In particular,
1
q
2
X
d
2
(V
i
(s), V
j
(t)) ≥ d
2
(V
i
, V
j
) −
ε
5
25
.
The lower bound can be improved if (V
i
, V
j
) is not ε-uniform.
Let
X
∗
ij
be the largest subset of
X
ij
that is the union of parts of
Q
. We may
assume
X
∗
ij
=
[
1≤s≤r
i
V
i
(s).
By an argument similar to the above, we have
1
r
i
r
j
X
1≤s≤r
i
1≤t≤r
j
d(V
i
(s), d
j
(t)) ≤ d(X
∗
ij
, X
∗
ji
) +
ε
5
49
.
By the choice of parts of
Q
within atoms, and because
|V
i
| ≥ qm
= 4
k
m
, we
have
|X
∗
ij
| ≥ |X
ij
| − 2
k−1
m
≥ |X
ij
|
1 −
2
k
m
ε|V
i
|
≥ |X
ij
|
1 −
1
2
k
ε
≥ |X
ij
|
1 −
ε
10
.
So by the lemma, we know
|d(X
∗
ij
, X
∗
ji
) − d(X
ij
, X
ji
)| <
ε
5
.
Recalling that
|d(X
ij
, X
ji
) − d(V
i
, V
j
)| > ε,
we have
1
r
i
r
j
X
1≤s≤r
i
1≤t≤r
j
d(V
i
(s), V
j
(t)) − d(V
i
, V
j
)
>
3
4
ε.
We can now allow our Cauchy–Schwarz inequality with
n
=
q
2
and
m
=
r
i
r
j
gives
1
q
2
X
1≤s,t≤q
d
2
(V
i
(s), V
j
(t)) ≥ d
2
(V
i
, V
j
) −
ε
5
25
+
r
i
r
j
q
2
·
9ε
2
16
≥ d
2
(V
i
, V
j
) −
ε
5
25
+
ε
4
3
,
using the fact that
r
i
q
≥
1 −
1
m
r
i
q
m + 1
m
≥
1 −
1
m
≥
|X
∗
ij
|
|V
i
|
≥
1 −
1
m
1 −
ε
10
|X
ij
|
|V
i
|
>
4ε
5
.
Therefore
ind(Q) =
1
k
2
q
2
X
1≤i<j<k
1≤s,t≤q
d
2
(V
i
(s), V
j
(t))
≥
1
k
2
X
1≤i<j≤k
d
2
(V
i
, V
j
) −
ε
5
25
+ ε
k
2
ε
4
3
≥ ind(P ) +
ε
5
8
.
The proof gives something like
L ∼ 2
2
.
.
.
2
,
where the tower is ε
−5
tall. Can we do better than that?
In 1997, Gowers showed that the tower of height at least
ε
−1/16
. More
generally, we can define
V
1
, . . . , V
k
to be (
ε, δ, η
)-uniform if all but
η
k
2
pairs
(
V
i
, V
j
) satisfy
|d
(
V
i
, V
j
)
− d
(
V
0
i
, V
0
j
)
| ≤ ε
whenever
|V
0
i
| ≥ δ|V
i
|
. Then there is a
graph for which every (1
− δ
1/16
, δ,
1
−
20
δ
1/16
)-uniform partition needs a tower
height δ
−1/16
parts.
More recently, Moskowitz and Shapira (2012) improved these bounds. Most
recently, a reformulation of the lemma due to Lov´asz and Szegedy (2007) for
which the upper bound is tower(
ε
−2
) was shown to have lower bound tower(
ε
−2
)
by Fox and Lov´asz (2014) (note that these are different Lov´asz’s!).
Let’s now turn to some applications of the Szemer´edi’s regularity lemma.
Recall that Ramsey’s theorem says there exists
R
(
k
) so every red-blue colouring
of the edges of
K
n
yeidls a monochromatic
K
k
provided
n ≥ R
(
k
). There are
known bounds
2
k/2
≤ R(k) ≤ 4
k
.
The existence of
R
(
k
) implies that for every graph
G
, there exists a number
r(G) minimal so if n ≥ r(G) and we colour K
n
, we obtain a monochromatic G.
Clearly, we have
r(G) ≤ R(|G|).
How much smaller can r(G) be compared to R(|G|)?
Theorem. Given an integer d, there exists c(d) such that
r(G) ≤ c|G|
for every graph G with ∆(G) ≤ d.
Proof.
Let
t
=
R
(
d
+ 1). Pick
ε ≤ min
n
1
t
,
1
2
d
(d+1)
o
. Let
` ≥ t
2
, and let
L = L(`, ε). We show that c =
L
ε
works.
Indeed, let
G
be a graph. Colour the edges of
K
n
by red and blue, where
n ≥ c|G|
. Apply Szemir´edi to the red graph with
`, ε
as above. Let
H
be
the graph whose vertices are
{V
1
, . . . , V
m
}
, where
V
1
, . . . , V
m
is the partition
of the red graph. Let
V
i
, V
j
∈ E
(
H
) if (
V
i
, V
j
) is
ε
-uniform. Notice that
m
=
|H| ≥ ` ≥ t
2
, and
e
(
¯
H
)
≤ ε
m
2
. So
H ⊇ K
t
, or else by Tur´an’s theroem,
there are integers d
1
, . . . , d
t−1
and
P
d
i
m and
e(
¯
H) ≥
d
i
2
≥ (t − 1)
m/(t − 1)
2
≥ ε
m
2
by our choice of ε and m.
We may as well assume all pairs
V
i
, V
j
for 1
≤ i < j ≤ t
are
ε
-uniform. We
colour the edge of
K
t
green if
d
(
V
i
, V
j
)
≥
1
2
(in the red graph), or white if
<
1
2
(i.e. density >
1
2
in the blue graph).
By Ramsey’s theorem, we may assume all pairs
V
i
V
j
for 1
≤ i < j ≤ d
+ 1
are the same colour. We may wlog assume the colour is green, and we shall find
a red G (a similar argument gives a blue G if the colour is white).
Indeed, take a vertex colouring of
G
with at most
d
+ 1 colours (using
∆(
G
)
≤ d
), with no colour used more than
|G|
times. By the building lemma
with
H
(in the lemma) being
G
(in this proof), and
G
(in the lemma) equal to
the subgrpah of the red graph spanned by V
1
, . . . , V
d+1
(here),
u = |V
i
| ≥
n
L
≥
c|G|
L
≥
|G|
ε
,
r = d + 1, λ =
1
2
, and we are done.
This proof is due to Chv´atal, R¨odl, Szem´eredi, Trotter (1983). It was extended
to more general graphs by Chen and Schelp (1993) including planar graphs. It
was conjectured by Burr and Erd¨os (1978) to be true for
d
-degenerate graphs
(e(H) ≤ d|H| for all H ⊆ G).
Kostochka–R¨odl (2004) introduced “dependent random choice”, used by
Fox–Sudakov (2009) and finally Lee (2015) proved the full conjecture.
An important application of the Szem´eredi regularity lemma is the triangle
removal lemma.
Theorem
(Triangle removal lemma)
.
Given
ε >
0, there exists
δ >
0 such that
if
|G|
=
n
and
G
contains at most
δn
3
triangles, then there exists a set of at
most εn
2
edges whose removal leaves no triangles.
Proof. Exercise. (See example sheet)
Appropriate modifications hold for general graphs, not just triangles.
Corollary
(Roth, 1950’s)
.
Let
ε >
0. Then if
n
is large enough, and
A ⊆
[
n
] =
{1, 2, . . . , n} with |A| ≥ εn, then A contains a 3-term arithmetic progression.
Roth originally proved this by some sort of Fourier analysis arguments, while
Szmer´edi came and prove this for all lengths later.
Proof. Define
B = {(x, y) ∈ [2n]
2
: x − y ∈ A}.
Then certainly
|B| ≥ εn
2
. We form a 3-partite graph with disjoint vertex classes
X
= [2
n
] and
Y
= [2
n
],
Z
= [4
n
]. If we have
x ∈ X, y ∈ Y
and
z ∈ Z
, we join
x
to y if (x, y) ∈ B; join x to z if (x, z − x) ∈ B and join y to z if (z − y, y) ∈ B.
A triangle in
G
is a triple (
x, y, z
) where (
x, y
)
,
(
x, y
+
w
)
,
(
x
+
w, y
)
∈ B
where
w
=
z − x − y
. Note that
w <
0 is okay. A 0-triangle is one with
w
= 0.
There are at least
εn
2
of these, one for each (
x, y
)
∈ B
, and these are edge
disjoint, because z = x + y.
Hence the triangles cannot be killed by removing
≤ εn
2
/
2 edges. By the
triangle removal lemma, we must have
≥ δn
3
triangles for some
δ
. In particular,
for n large enough, there is some triangle that is not a 0-triangle.
But then we are done, since
x − y − w, x − y, x − y + w ∈ A
where w 6= 0, and this is a 3-term arithemtic progression.
There is a simple generalization of this argument which yields
k
-term arith-
metic progressions provided we have a suitable removal lemma. This needs a
Szemer´edi regularity lemma for (
k −
1)-uniform hypergraphs, instead of just
graphs, and a corresponding version of the building lemma.
The natural generalizations of Szemer´edi’s lemma to hypergraphs is easily
shown to be true (exercise). The catch is that what the Szemer´edi’s lemma does
not give us a strong enough result to apply the building lemma.
What we need is a stronger version of the regularity that allows us to build
graphs, but not too strong that we can’t prove the Szemer´edi regularity lemma.
A workable hypergraph regularity lemma along these lines was proved by Nagle,
R¨odl, Skokan, and by Gowers (those weren’t quite the same lemma, though).