Part III — Extremal Graph Theory
Based on lectures by A. G. Thomason
Notes taken by Dexter Chua
Michaelmas 2017
These notes are not endorsed by the lecturers, and I have modified them (often
significantly) after lectures. They are nowhere near accurate representations of what
was actually lectured, and in particular, all errors are almost surely mine.
Tur´an’s theorem, giving the maximum size of a graph that contains no complete
r
-vertex subgraph, is an example of an extremal graph theorem. Extremal graph theory
is an umbrella title for the study of how graph and hypergraph properties depend on
the values of parameters. This course builds on the material introduced in the Part
II Graph Theory course, which includes Tur´an’s theorem and also the Erd¨os–Stone
theorem.
The first few lectures will cover the Erd¨os–Stone theorem and stability. Then we
shall treat Szemer´edi’s Regularity Lemma, with some applications, such as to hered-
itary properties. Subsequent material, depending on available time, might include:
hypergraph extensions, the flag algebra method of Razborov, graph containers and
applications.
Pre-requisites
A knowledge of the basic concepts, techniques and results of graph theory, as afforded
by the Part II Graph Theory course, will be assumed. This includes Tur´an’s theorem,
Ramsey’s theorem, Hall’s theorem and so on, together with applications of elementary
probability.
1 The Erd¨os–Stone theorem
The starting point of extremal graph theory is perhaps Tur´an’s theorem, which
you hopefully learnt from the IID Graph Theory course. To state the theory, we
need the following preliminary definition:
Definition
(Tur´an graph)
.
The Tur´an graph
T
r
(
n
) is the complete
r
-partite
graph on
n
vertices with class sizes
bn/rc
or
dn/re
. We write
t
r
(
n
) for the
number of edges in T
r
(n).
The theorem then says
Theorem
(Tur´an’s theorem)
.
If
G
is a graph with
|G|
=
n
,
e
(
G
)
≥ t
r
(
n
) and
G 6⊇ K
r+1
. Then G = T
r
(n).
This is an example of an extremal theorem. More generally, given a fixed
graph F , we seek
ex(n, F ) = max{e(G) : |G| = n, G 6⊇ F }.
Tur´an’s theorem tells us
ex
(
n, K
r+1
) =
t
r
(
n
). We cannot find a nice expression
for the latter number, but we have
ex(n, K
r+1
) = t
r
(n) ≈
1 −
1
r
n
2
.
Tur´an’s theorem is a rather special case. First of all, we actually know the exact
value of
ex
(
n, F
). Moreover, there is a unique extremal graph realizing the bound.
Both of these properties do not extend to other choices of F .
By definition, if
e
(
G
)
> ex
(
n, K
r+1
), then
G
contains a
K
r+1
. The Erd¨os–
Stone theorem tells us that as long as
|G|
=
n
is big enough, this condition
implies G contains a much larger graph than K
r+1
.
Notation.
We denote by
K
r
(
t
) the complete
r
-partite graph with
t
vertices in
each class.
So K
r
(1) = K
r
and K
r
(t) = T
r
(rt).
Theorem
(Erd¨os–Stone, 1946)
.
Let
r ≥
1 be an integer and
ε >
0. Then there
exists d = d(r, ε) and n
0
= n
0
(r, ε) such that if |G| = n ≥ n
0
and
e(G) ≥
1 −
1
r
+ ε
n
2
,
then G ⊇ K
r+1
(t), where t = bd log nc.
Note that we can remove
n
0
from the statement simply by reducing
d
, since
for sufficiently small d, whenever n < n
0
, we have bd log nc = 0.
One corollary of the theorem, and a good way to think about the theorem is
that given numbers
r, ε, t
, whenever
|G|
=
n
is sufficiently large, the inequality
e(G) ≥
1 −
1
r
+ ε
n
2
implies G ⊆ K
r+1
(t).
To prove the Erd¨os–Stone theorem, a natural strategy is to try to throw away
vertices of small degree, and so that we can bound the minimal degree of the
graph instead of the total number of edges. We will make use of the following
lemma to do so:
Lemma.
Let
c, ε >
0. Then there exists
n
1
=
n
1
(
c, ε
) such that if
|G|
=
n ≥ n
1
and
e
(
G
)
≥
(
c
+
ε
)
n
2
, then
G
has a subgraph
H
where
δ
(
H
)
≥ c|H|
and
|H| ≥
√
εn.
Proof.
The idea is that we can keep removing the vertex of smallest degree and
then we must eventually get the
H
we want. Suppose this doesn’t gives us a
suitable graph even after we’ve got
√
εn
vertices left. That means we can find a
sequence
G = G
n
⊇ G
n−1
⊇ G
n−2
⊇ ···G
s
,
where
s
=
bε
1/2
nc
,
|G
j
|
=
j
and the vertex in
G
j
\ G
j−1
has degree
< cj
in
G
j
.
We can then calculate
e(G
s
) > (c + ε)
n
2
− c
n
X
j=s+1
j
= (c + ε)
n
2
− c
n + 1
2
−
s + 1
2
∼
εn
2
2
as
n
gets large (since
c
and
s
are fixed numbers). In particular, this is
>
s
2
.
But G
s
only has s vertices, so this is impossible.
Using this, we can reduce the Erd¨os–Stone theorem to a version that talks
about the minimum degree instead.
Lemma.
Let
r ≥
1 be an integer and
ε >
0. Then there exists a
d
1
=
d
1
(
r, ε
)
and n
2
= n
2
(r, ε) such that if |G| = n ≥ n
2
and
δ(G) ≥
1 −
1
r
+ ε
n,
then G ⊇ K
r+1
(t), where t = bd
1
log nc.
We first see how this implies the Erd¨os–Stone theorem:
Proof of Erd¨os–Stone theorem.
Provided
n
0
is large, say
n
0
> n
1
1 −
1
r
+
ε
2
,
ε
2
,
we can apply the first lemma to
G
to obtain a subgraph
H ⊆ G
where
|H| >
p
ε
2
n
,
and δ(H) ≥
1 −
1
r
+
ε
2
|H|.
We can then apply our final lemma as long as
p
ε
2
n
is big enough, and obtain
K
r+1
(t) ⊆ H ⊆ G, with t >
d
1
(r, ε/2) log
p
ε
2
n
.
We can now prove the lemma.
Proof of lemma.
We proceed by induction on
r
. If
r
= 0 or
ε ≥
1
r
, the theorem
is trivial. Otherwise, by the induction hypothesis, we may assume
G ⊇ K
r
(
T
)
for
T =
2t
εr
.
Call it K = K
r
(T ). This is always possible, as long as
d
1
(r, ε) <
εr
2
d
1
r −1,
1
r(r − 1)
.
The exact form is not important. The crucial part is that
1
r(r−1)
=
1
r−1
−
1
r
,
which is how we chose the ε to put into d
1
(r −1, ε).
Let
U
be the set of vertices in
G − K
having at least
1 −
1
r
+
ε
2
|K|
neigh-
bours in K. Calculating
1 −
1
r
+
ε
2
|K| =
1 −
1
r
+
ε
2
rT = (r − 1)T +
εr
2
T ≥ (r − 1)T + t,
we see that every element in
U
is joined to at least
t
vertices in each class, and
hence is joined to some K
r
(t) ⊆ K.
So we have to show that
|U|
is large. If so, then by a pigeonhole principle
argument, it follows that we can always find enough vertices in
U
so that adding
them to K gives a K
r+1
(t).
Claim.
There is some
c >
0 (depending on
r
and
ε
) such that for
n
sufficiently
large, we have
|U| ≥ cn.
The argument to establish these kinds of bounds is standard, and will be
used repeatedly. We write
e
(
K, G − K
) for the number of edges between
K
and
G − K
. By the minimum degree condition, each vertex of
K
sends at least
1 −
1
r
+ ε
n − |K| edges to G − K. Then we have two inequalities
|K|
1 −
1
r
+ ε
n − |K|
≤ e(K, G − K)
≤ |U ||K|+ (n − |U|)
1 −
1
r
+
ε
2
|K|.
Rearranging, this tells us
εn
2
− |K| ≤ |U |
1
r
−
ε
2
.
Now note that
|K| ∼ log n
, so for large
n
, the second term on the left is negligible,
and it follows that U ∼ n.
We now want to calculate the number of
K
r
(
t
)’s in
K
. To do so, we use the
simple inequality
n
k
≤
en
k
k
.
Then we have
#K
r
(t) =
T
t
r
≤
eT
t
rt
≤
3e
εr
rt
≤
3e
εr
rd log n
= n
rd log(3e/εr)
Now if we pick
d
sufficiently small, then this tells us #
K
r
(
t
) grows sublinearly
with
n
. Since
|U|
grows linearly, and
t
grows logarithmically, it follows that for
n large enough, we have
|U| ≥ t · #K
r
(t).
Then by the pigeonhole principle, there must be a set
W ⊆ U
of size
t
joined to
the same K
r
(t), giving a K
r+1
(t).
Erd¨os and Simonovits noticed that Erd¨os–Stone allows us to find
ex
(
n, F
)
asymptotically for all F .
Theorem
(Erd¨os–Simonovits)
.
Let
F
be a fixed graph with chromatic number
χ(F ) = r + 1. Then
lim
n→∞
ex(n, F )
n
2
= 1 −
1
r
.
Proof.
Since
χ
(
F
) =
r
+ 1, we know
F
cannot be embedded in an
r
-partite
graph. So in particular, F 6⊆ T
r
(n). So
ex(n, F ) ≥ t
r
(n) ≥
1 −
1
r
n
2
.
On the other hand, given any ε > 0, if |G| = n and
e(G) ≥
1 −
1
r
+ ε
n
2
,
then by the Erd¨os–Stone theorem, we have
G ⊇ K
r+1
(
|F |
)
⊇ F
provided
n
is
large. So we know that for every ε > 0, we have
lim sup
ex(n, F )
n
2
≤ 1 −
1
r
+ ε.
So we are done.
If
r >
1, then this gives us a genuine asymptotic expression for
ex
(
n, F
).
However, if
r
= 1, i.e.
F
is a bipartite graph, then this only tells us
ex
(
n, F
) =
o
n
2
, but doesn’t tell us about the true asymptotic behaviour.
To end the chapter, we show that
t ∼ log n
is indeed the best we can do in
the Erd¨os–Stone theorem, by actually constructing some graphs.
Theorem.
Given
r ∈ N
, there exists
ε
r
>
0 such that if 0
< ε < ε
r
, then there
exists n
3
(r, ε) so that if n > n
3
, there exists a graph G of order n such that
e(G) ≥
1 −
1
r
+ ε
n
2
but K
r+1
(t) 6⊆ G, where
t =
3 log n
log 1/ε
.
So this tells us we cannot get better than
t ∼ log n
, and this gives us some
bound on d(r, ε).
Proof.
Start with the Tur´an graph
T
r
(
n
). Let
m
=
n
r
. Then there is a class
W
of
T
r
(
n
) of size
m
. The strategy is to add
ε
n
2
edges inside
W
to obtain
G
such that
G
[
W
] (the subgraph of
G
formed by
W
) does not contain a
K
2
(
t
). It
then follows that G 6⊇ K
r+1
(t), but also
e(G) ≥ t
r
(n) + ε
n
2
≥
1 −
1
r
+ ε
n
2
,
as desired.
To see that such an addition is possible, we choose edges inside
W
indepen-
dently with probability
p
, to be determined later. Let
X
be the number of edges
chosen, and
Y
be the number of
K
2
(
t
) created. If
E
[
X − Y
]
> ε
n
2
, then this
means there is an actual choice of edges with
X − Y > ε
n
2
. We then remove
an edge from each
K
2
(
t
) to leave a
K
2
(
t
)-free graph with at least
X −Y > ε
n
2
edges.
So we want to actually compute
E
[
X − Y
]. Seeing that asymptotically,
m
is
much larger than t, we have
E[X − Y ] = E[X] − E[Y ]
= p
m
2
−
1
2
m
t
m − t
t
p
t
2
∼
1
2
pm
2
−
1
2
m
2t
p
t
2
=
1
2
pm
2
(1 − m
2t−2
p
t
2
−1
)
=
1
2
pm
2
(1 − (m
2
p
t+1
)
t−1
).
We pick p = 3εr
2
and ε
r
= (3r
2
)
−6
. Then p < ε
5/6
, and
m
2
p
t+1
< m
2
ε
5/6(t+1)
< (m
2
m
−5/2
)
t−1
<
1
2
.
Hence, we find that
E[x − y] ≥
1
4
pm
2
> ε
n
2
.
Let’s summarize what we have got so far. Let
t
(
n, r, ε
) be the largest value
of
t
such that a graph of order
n
with
1 −
1
r
+ ε
n
2
edges is guaranteed to
contain
K
r+1
(
t
). Then we know
t
(
n, r, ε
) grows with
n
like
log n
. If we are keen,
we can ask how t depends on the other terms r and ε. We just saw that
t(n, r, ε) ≤
3 log n
log 1/ε
.
So we see that the dependence on
ε
is at most logarithmic, and in 1976, Bollob´as,
Erd¨os and Simonovits showed that
t(n, r, ε) ≥ c
log n
r log 1/ε
for some c. Thus, t(n, r, ε) also grows (inverse) logarithmically with ε.
In our original bound, there is no dependence on
r
, which is curious. While
Bollob´as, Erd¨os and Simonovits’s bound does, in 1978, Chv´atal and Szemer´edi
showed that
t ≥
1
500
log n
log 1/ε
if n is large. So we know there actually is no dependence on r.
We can also ask about the containment of less regular graphs than
K
r
(
t
). In
1994, Bollob´as and Kohayakawa adapted the proof of the Erd¨os–Stone theorem
to show that there is a constant
c
such that for any 0
< γ <
1, if
e
(
G
)
≥
1 −
1
r
+ ε
n
2
and
n
is large, then we can find a complete (
r
+ 1)-partite
subgraph with class sizes
cγ
log n
r log 1/ε
,
cγ
log n
log r
, r − 1 times,
j
cε
3
2
−
γ
2
n
1−γ
k
.
We might wonder if we can make similar statements for hypergraphs. It turns
out all the analogous questions are open. Somehow graphs are much easier.
2 Stability
An extremal problem is stable if every near-optimal extremal example looks close
to some optimal (unique) example. Stability pertain for ex(n, F ).
Theorem. Let t, r ≥ 2 be fixed, and suppose |G| = n and G 6⊇ K
r+1
(t). If
e(G) =
1 −
1
r
+ o(1)
n
2
.
Then
(i) There exists T
r
(n) on V (G) with |E(G)∆E(T
r
(n))| = o(n
2
).
(ii) G contains an r-partite subgraph with
1 −
1
r
+ o(1)
n
2
edges.
(iii) G contains an r-partite subgraph with minimum degree
1 −
1
r
+ o(1)
n.
The outline of the proof is as follows: we first show that the three statements
are equivalent, so that we only have to prove (ii). To prove (ii), we first use
Erd¨os–Stone to find some
K
r
(
s
) living inside
G
(for some
s
), which is a good
r
-partite subgraph of
G
, but with not quite the right number of vertices. We
now look at the remaining vertices. For each vertex
v
, find the
C
i
such that
v
is
connected to as few vertices in
C
i
as possible, and enlarge
C
i
to include that
as well. After doing this,
C
i
will have quite a few edges between its vertices,
and we throw those away. The hope is that there are only
o
(
n
2
) edges to throw
away, so that we still have
1 −
1
r
+ o(1)
n
2
edges left. It turns out as long as
we throw out some “bad” vertices, we will be fine.
Proof.
We first prove (ii), which looks the weakest. We will then argue that the
others follow from this (and in fact they are equivalent).
By Erd¨os–Stone, we can always find some
K
r
(
s
) =
K ⊆ G
for some
s
=
s
(
n
)
→ ∞
. We can, of course, always choose
s
(
n
) so that
s
(
n
)
≤ log n
, which
will be helpful for our future analysis. We let C
i
be the ith class of K.
– By throwing away o(n) vertices, we may assume that
δ(G) ≥
1 −
1
r
+ o(1)
n
–
Let
X
be the set of all vertices joined to at least
t
vertices in each
C
i
. Note
that there are
s
t
r
many copies of
K
r
(
t
)’s in
K
. So by the pigeonhole
principle, we must have
|X| < t
s
t
r
=
o
(
n
), or else we can construct a
K
r+1
(t) inside G.
–
Let
Y
be the set of vertices joined to fewer than (
r −
1)
s −
s
2t
+
t
other
vertices. By our bound on δ(G), we certainly have
e(K, G − K) ≥ s(r − 1 + o(1))n.
On the other hand, every element of
G
is certainly joined to at most
(r −1)s + t edges, since X was thrown away. So we have
((r −1)s + t)(n −|Y |) + |Y |
(r −1)s −
s
2t
+ t
≥ e(K, G − K).
So we deduce that |Y | = o(n). Throw Y away.
Let
V
i
be the set of vertices in
G \ K
joined to fewer than
t
of
C
i
. It is now
enough to show that
e
(
G
[
V
i
]) =
o
(
n
2
). We can then throw away the edges in
each V
i
to obtain an r-partite graph.
Suppose on the contrary that
e
(
G
[
V
j
])
≥ εn
2
, say, for some
j
. Then Erd¨os–
Stone with
r
= 1 says we have
G
[
V
j
]
⊇ K
2
(
t
). Each vertex of
K
2
(
t
) has at
least
s −
s
2t
+ 1 in each other
C
i
, for
i 6
=
j
. So we see that
K
2
(
t
) has at least
s − 2t
s
2t
− 1
> t common neighbours in each C
i
, giving K
r+1
(t) ⊆ G.
It now remains to show that (i) and (iii) follows from (ii). The details are
left for the example sheet, but we sketch out the rough argument. (ii)
⇒
(i) is
straightforward, since an
r
-partite graph with that many edges is already pretty
close to being a Tur´an graph.
To deduce (iii), since we can assume
δ
(
G
)
≥
1 −
1
r
+ o(1)
n
, we note that if
(iii) did not hold, then we have
εn
vertices of degree
≤
1 −
1
r
− ε
n
, and their
removal leaves a graph of order (1 − ε)n with at least
1 −
1
r
+ o(1)
n
2
− εn
1 −
1
r
− ε
n >
1 −
1
r
+ ε
2
(1 − ε)n
2
,
which by Erd¨os–Stone would contain K
r+1
(t). So we are done.
Corollary.
Let
χ
(
F
) =
r
+ 1, and let
G
be extremal for
F
, i.e.
G 6⊇ F
and
e(G) = ex(|G|, F ). Then δ(G) =
1 −
1
r
+ o(1)
n.
Proof.
By our asymptotic bound on
ex
(
n, F
), it cannot be that
δ
(
G
) is
greater than
1 −
1
r
+ o(1)
n
. So there must be a vertex
v ∈ G
with
d(v) ≤
1 −
1
r
− ε
n.
We now apply version (iii) of the stability theorem to obtain an
r
-partite
subgraph
H
of
G
. We can certainly pick
|F |
vertices in the same part of
H
,
which are joined to
m
=
1 −
1
r
+ o(1)
common neighbours. Form
G
∗
from
G − v
by adding a new vertex
u
joined to these
m
vertices. Then
e
(
G
∗
)
> e
(
G
),
and so the maximality of G entails G
∗
⊇ F .
Pick a copy of
F
in
G
∗
. This must involve
u
, since
G
, and hence
G − v
does
not contain a copy of
F
. Thus, there must be some
x
amongst the
|F |
vertices
mentioned. But then we can replace u with x and we are done.
Sometimes, stability and bootstrapping can give exact results.
Example. ex
(
n, C
5
) =
t
2
(
n
). In fact,
ex
(
n, C
2k+1
) =
t
2
(
n
) if
n
is large enough.
Theorem
(Simonovits)
.
Let
F
be (
r
+ 1)-edge-critical, i.e.
χ
(
F
) =
r
+ 1 but
χ(F ) \ e) = r for every edge e of F . Then for large n,
ex(n, F ) = t
r
(n).
and the only extremal graph is T
r
(n).
So we get a theorem like Tur´an’s theorem for large n.
Proof.
Let
G
be an extremal graph for
F
and let
H
be an
r
-partite subgraph
with
δ(H) =
1 −
1
r
+ o(1)
n.
Note that
H
necessarily have
r
parts of size
1
r
+ o(1)
n
each. Assign each of
the o(n) vertices in V (G) \ V (H) to a class where it has fewest neighbours.
Suppose some vertex
v
has
εn
neighbours in its own class. Then it has
≥ εn
in each class. Pick
εn
neighbours of
v
in each class of
H
. These neighbours span
a graph with at least
1 −
1
r
+ o(1)
rεn
2
edges. So by Erd¨os–Stone (or arguing
directly), they span
F − w
for some vertex
w
(contained in
K
r
(
|F |
)). Hence
G ⊇ F , contradiction.
Thus, each vertex of
G
has only
o
(
n
) vertices in its own class. So it is joined
to all but o(n) vertices in every other class.
Suppose some class of
G
contains an edge
xy
. Pick a set
Z
of
|F |
vertices
in that class with
{x, y} ∈ Z
. Now
Z
has
1
r
+ o(1)
n
common neighbours in
each class, so (by Erd¨os–Stone or directly) these common neighbours span a
K
r−1
(
|F |
). But together with
Z
, we have a
K
r
(
|F |
) but with an edge added
inside a class. But by our condition that
F \e
is
r
-partite for any
e
, this subgraph
contains an F . This is a contradiction.
So we conclude that no class of
G
contains an edge. So
G
itself is
r
-partite,
but the
r
-partite graph with most edges is
T
r
(
n
), which does not contain
F
. So
G = T
r
(n).
3 Supersaturation
Suppose we have a graph
G
with
e
(
G
)
> ex
(
n, F
). Then by definition, there is
at least one copy of
F
in
G
. But can we tell how many copies we have? It turns
out this is not too difficult to answer, and in fact we can answer the question for
any hypergraph.
Recall that an
`
-uniform hypergraph is a pair (
V, E
), where
E ⊆ V
(`)
. We
can define the extremal function of a class of hypergraphs F by
ex(n, F) = max{e(G) : |G| = n, G contains no f ∈ F}.
Again we are interested in the limiting density
π(F) = lim
n→∞
ex(n, F)
n
`
.
It is an easy exercise to show that this limit always exists. We solved it explicitly
for graphs explicitly previously, but we don’t really need the Erd¨os–Stone theorem
just to show that the limit exists.
The basic theorem in supersaturation is
Theorem
(Erd¨os–Simonovits)
.
Let
H
be some
`
-uniform hypergraph. Then
for all
ε >
0, there exists
δ
(
H, ε
) such that every
`
-uniform hypergraph
G
with
|G| = n and
e(G) > (π(H) + ε)
n
`
contains bδn
|H|
c copies of H.
Note that
n
|H|
is approximately the number of ways to choose
|H|
vertices
from n, so it’s the number of possible candidates for subgraphs H.
Proof.
For each
m
-set
M ⊆ V
(
G
), we let
G
[
M
] be the sub-hypergraph induced
by these vertices. Let the number of subsets
M
with
e
(
G
[
M
])
>
π(H) +
ε
2
m
`
be η
n
m
. Then we can estimate
(π(H) + ε)
n
`
≤ e(G) =
P
M
e(G[M])
n−`
m−`
≤
η
n
m
m
`
+ (1 − η)
n
m
π(H) +
ε
2
m
`
n−`
m−`
.
So if n > m, then
π(H) + ε ≤ η + (1 + η)
π(H) +
ε
2
.
So
η ≥
ε
2
1 − π(H) −
ε
2
> 0.
The point is that it is positive, and that’s all we care about.
We pick m large enough so that
ex(m, H) <
π(H) +
ε
2
m
`
.
Then H ⊆ G[M] for at least η
n
m
choices of M. Hence G contains at least
η
n
m
n−|H|
m−|H|
=
η
n
|H|
m
|H|
copies of
H
, and we are done. (Our results hold when
n
is large enough, but we
can choose δ small enough so that δn
|H|
< 1 when n is small)
Let
k
P
(
G
) be the number of copies of
K
p
in
G
. Ramsey’s theorem tells us
k
p
(
G
) +
k
p
(
¯
G
)
>
0 if
|G|
is large (where
¯
G
is the complement of
G
). In the
simplest case where
p
= 3, it turns out we can count these monochromatic
triangles exactly.
Theorem (Lorden, 1961). Let G have degree sequence d
1
, . . . , d
n
. Then
k
3
(G) + k
3
(
¯
G) =
n
3
− (n − 2)e(G) +
n
X
i=1
d
i
2
.
Proof. The number of paths of length 2 in G and
¯
G is precisely
n
X
i=1
d
i
2
+
n − 1 − d
i
2
= 2
n
X
i=1
d
i
2
− 2(n − 2)e(G) + 3
n
3
,
since to find a path of length 2, we pick the middle vertex and then pick the
two edges. A complete or empty
K
3
contains 3 such paths; Other sets of three
vertices contain exactly 1 such path. Hence
n
3
+ 2(k
3
(G) + k
3
(
¯
G)) = number of paths of length 2.
Corollary (Goodman, 1959). We have
k
3
(G) + k
3
(
¯
G) ≥
1
24
n(n − 1)(n − 5).
In particular, the Ramsey number of a triangle is at most 6.
Proof. Let m = e(G). Then
k
3
(G) + k
3
(
¯
G) ≥
n
3
− (n − 2)m + n
2m/n
2
.
Then minimize over m.
This shows the minimum density of a monochromatic
K
3
in a red/blue
colouring of
K
n
(for
n
large) is
∼
1
4
. But if we colour edges monochromatic, then
1
4
is the probability of having a triangle being monochromatic. So the density
is achieved by a “random colouring”. Recall also that the best bounds on the
Ramsey numbers we have are obtained by random colourings. So we might think
the best way of colouring if we want to minimize the number of monochromatic
cliques is to do so randomly.
However, this is not true. While we do not know what the minimum density
of monochromatic
K
4
in a red/blue colouring of
K
n
, it is already known to be
<
1
33
(while
1
32
is what we expect from a random colouring). It is also known by
flag algebras to be >
1
35
. So we are not very far.
Corollary. For m = e(G) and n = |G|, we have
k
3
(G) ≥
m
3n
(4m − n
2
).
Proof. By Lorden’s theorem, we know
k
3
(G) + k
3
(
¯
G) =
n
3
− (n − 2)e(
¯
G) +
X
¯
d
i
2
,
where
¯
d
i
is the degree sequence in
¯
G. But
3k
3
(
¯
G) ≤
X
¯
d
i
2
,
since the sum is counting the number of paths of length 2. So we find that
k
3
(G) ≥
n
3
− (n − 2) ¯m −
2
3
n
2 ¯m/n
2
,
and ¯m =
n
2
− m.
Observe that equality is almost never attained. It is attained only for regular
graphs with no subgraphs looking like
So non-adjacency is an equivalence relation, so the graph is complete multi-partite
and regular. Thus it is T
r
(n) with r | n.
Theorem.
Let
G
be a graph. For any graph
F
, let
i
F
(
G
) be the number of
induced copies of
F
in
G
, i.e. the number of subsets
M ⊆ V
(
G
) such that
G[M]
∼
=
F . So, for example, i
K
p
(G) = k
p
(G).
Define
f(G) =
X
F
α
F
i
F
(G),
with the sum being over a finite collection of graphs
F
, each being complete
multipartite, with
α
F
∈ R
and
α
F
≥
0 if
F
is not complete. Then amongst
graphs of given order,
f
(
G
) is maximized on a complete multi-partite graph.
Moreover, if α
¯
K
3
> 0, then there are no other maxima.
Proof.
We may suppose
α
¯
K
3
>
0, because the case of
α
¯
K
3
= 0 follows from a
limit argument. Choose a graph
G
maximizing
f
and suppose
G
is not complete
multipartite. Then there exist non-adjacent vertices
x, y
whose neighbourhoods
X, Y differ.
There are four contributions to i
F
(G), coming from
(i) F ’s that contain both x and y;
(ii) F ’s that contain y but not x;
(iii) F ’s that contain x but not y;
(iv) F ’s that contain neither x nor y.
We may assume that the contribution from (iii)
≥
(ii), and if they are equal,
then |X| ≤ |Y |.
Consider what happens when we remove all edges between
y
and
Y
, and add
edges from y to everything in X. Clearly (iii) and (iv) are unaffected.
–
If (iii)
>
(ii), then after this move, the contribution of (ii) becomes equal to
the contribution of (iii) (which didn’t change), and hence strictly increased.
The graphs
F
that contribute to (i) are not complete, so
α
F
≥
0. Moreover,
since
F
is complete multi-partite, it cannot contain a vertex in
X
∆
Y
. So
making the move can only increase the number of graphs contributing to
(i), and each contribution is non-negative.
–
If (iii) = (ii) and
|X| ≤ |Y |
, then we make similar arguments. The
contribution to (ii) is unchanged this time, and we know the contribution
of (i) strictly increased, because the number of
¯
K
3
’s contributing to (i) is
the number of points not connected to x and y.
In both cases, the total sum increased.
Perhaps that theorem seemed like a rather peculiar one to prove. However,
it has some nice consequences. The following theorem relates
k
p
(
G
) with
k
r
(
G
)
for different p and r:
Theorem
(Bollob´as, 1976)
.
Let 1
≤ p ≤ r
, and for 0
≤ x ≤
n
p
, let
ψ
(
x
) be a
maximal convex function lying below the points
{(k
p
(T
q
(n)), k
r
(T
q
(n))) : q = r − 1, r, . . .} ∪ {(0, 0)}.
Let G be a graph of order n. Then
k
r
(G) ≥ ψ(k
p
(G)).
Proof. Let f (G) = k
p
(G) − ck
r
(G), where c > 0.
Claim. It is enough to show that f is maximized on a Tur´an graph for any c.
Indeed, suppose we plot out the values of (k
p
(T
q
(n)), k
r
(T
q
(n)):
k
p
(G)
k
r
(G)
k
p
(T
r−1
(n))
k
p
(T
r
(n))
k
r
(T
r
(n))
k
p
(T
r+1
(n))
k
r
(T
r+1
(n))
If the theorem doesn’t hold, then we can pick a
G
such that (
k
p
(
G
)
, k
r
(
G
))
lies below
ψ
. Draw a straight line through the point with slope parallel to
ψ
. This
has slope
1
c
>
0 for some
c
. The intercept on the
x
-axis is then
k
p
(
G
)
− ck
r
(
G
),
which would be greater than
f
(
any Tur´an graph
) by convexity, a contradiction.
Now the previous theorem immediately tells us
f
is maximized on some
complete multi-partite graph. Suppose this has
q
class, say of sizes
a
1
≤ a
2
≤
··· ≤ a
q
. It is easy to verify
q ≥ r −
1. In fact, we may assume
q ≥ r
, else the
maximum is on a Tur´an graph T
r−1
(n).
Then we can write
f(G) = a
1
a
q
A − ca
q
a
q
B + C,
where
A, B, C
are rationals depending only on
a
2
, . . . , a
q−1
and
a
1
+
a
q
(
A
and
B
count the number of ways to pick a
K
p
and
K
r
respectively in a way that
involves terms in both the first and last classes).
We wlog assume c is irrational. Hence a
q
a
q
A − ca
1
a
q
= a
1
a
q
(A − cB) 6= 0.
–
If
A−cB <
0, replace
a
1
and
a
q
by 0 and
a
1
+
a
q
. This would then increase
f, which is impossible.
–
If
A −cB >
0 and
a
1
≤ a
q
−
2, then we can replace
a
1
, a
q
by
a
1
+ 1
, a
q
−
1
to increase f .
Hence a
1
≥ a
q
− 1. So G = T
q
(n).
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 = N16
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).
5 Subcontraction, subdivision and linking
We begin with some definitions.
Definition.
Let
G
be a graph,
e
=
xy
an edge. Then the graph
G/e
is the
graph formed from
G \{x, y}
by adding a new vertex joined to all neighbours of
x and y. We say this is the graph formed by contracting the edge e.
Definition
((Sub)contraction)
.
A contraction of
G
is a graph obtained by a
sequence of edge contractions. A subcontraction of
G
is a contraction of a
subgraph. We write G H if H is a subcontraction of G.
If
G H
, then
G
has disjoint vertex subsets
W
v
for each
v ∈ V
(
H
) such that
G
[
W
v
] is connected, and there is an edge of
G
between
W
u
and
W
v
if
w ∈ E
(
H
).
Definition
(Subdivision)
.
If
H
is a graph,
T H
stands for any graph obtained
from
H
by replacing its edges by vertex disjoint paths (i.e. we subdivide edges).
The
T
stands for “topological”, since the resulting graph has the same
topology.
Clearly, if G ⊇ T H, then G H.
Recall the following theorem:
Theorem
(Menger’s theorem)
.
Let
G
be a graph and
s
1
, . . . , s
k
, t
1
, . . . , t
k
be
distinct vertices. If
κ
(
G
)
≥ k
, then there exists
k
vertex disjoint paths from
{s
1
, . . . , s
k
} to {t
1
, . . . , t
k
}.
This is good, but not good enoguh. It would be nice if we can have paths
that join s
i
to t
i
, as opposed to joining s
i
to any element in {t
1
, . . . , t
k
}.
Definition
(
k
-linked graph)
.
We say
G
is
k
-linked if there exists vertex disjoint
s
i
-t
i
paths for 1 ≤ i ≤ k for any choice of these 2k vertices.
We want to understand how these three notions interact. There are some
obvious ways in which they interact. For example, it is not hard to see that
G ⊇ T K
t
if G is k-linked for some large k. Here is a kind of converse.
Lemma. If κ(G) ≥ 2k and G ⊇ T K
5k
, then G is k-linked.
Proof.
Let
B
be the set of “branch vertices” of
T K
5k
, i.e. the 5
k
vertices
joined by paths. By Menger’s theorem, there exists 2
k
vertex disjoint paths
joining
{s
1
, . . . , s
k
, t
1
, . . . , t
k
}
to
B
(note that these sets might intersect). We
say one of our 2
k
paths impinges on a path in
T K
5k
if it meets that path and
subsequently leaves it. Choose a set of 2
k
paths impinging minimally (counting
1 per impingement).
Let these join
{s
1
, . . . , t
k
}
to
{v
1
, . . . , v
2k
}
, where
B
=
{v
1
, . . . , v
5k
}
. Then
no path impinges on a path in
T K
5k
from
{v
1
, . . . , v
2k
}
to
{v
2k+1
, . . . , v
5k
}
.
Otherwise, pick the path impinging closest to
v
2k+j
, and reroute it to
v
2k+j
rather than to something in
{v
1
, . . . , v
2k
}
, reducing the number of impingements.
Hence each path (of any 2
k
) meet at most one path in
{v
1
, . . . , v
2k
}
to
{v
2k+1
, . . . , v
5k
} (once we hit it, we must stay there).
Thus, we may assume the paths from
{v
1
, . . . , v
2k
}
to
{v
4k+1
, . . . , v
5k
}
are
not met at all. Then we are done, since we can link up
v
j
to
v
k+j
via
v
4k+j
to
join s
j
to t
k
.
The argument can be improved to use T K
3k
.
Since we are doing extremal graph theory, we want to ask the following
question — how many edges do we need to guarantee G K
t
or G ⊇ T K
t
?
For two graphs
G
and
H
, we write
G
+
H
for the graph formed by taking the
disjoint union of
G
and
H
and then joining everything in
G
to everything in
H
.
Lemma.
If
e
(
G
)
≥ k|G|
, then there exists some
H
with
|H| ≤
2
k
and
δ
(
H
)
≥ k
such that G K
1
+ H.
Proof.
Consider the minimal subcontraction
G
0
of
G
among those that satisfy
e
(
G
0
)
≥ k|G
0
|
. Then we must in fact have
e
(
G
0
) =
k|G
0
|
, or else we can just
throw away an edge.
Since
e
(
G
0
) =
k|G
0
|
, it must be the case that
δ
(
G
0
)
≤
2
k
. Let
v
be of
minimum degree in
G
0
. and set
H
=
G
0
[Γ(
v
)]. Then
G K
1
+
H
and
|H| ≤
2
v
.
To see that
δ
(
H
)
≥ k
, suppose
u ∈ V
(
H
) = Γ(
v
). Then by minimality of
G
0
,
we have
e(G
0
/uv) ≤ k|G
0
| − k − 1.
But the number of edges we kill when performing this contraction is exactly 1
plus the number of triangles containing
uv
. So
uv
lies in at least
k
triangles of
G
0
. In other words, δ(H) ≥ k.
By iterating this, we can find some subcontractions into K
t
.
Theorem. If t ≥ 3 and e(G) ≥ 2
t−3
|G|, then G K
t
.
Proof.
If
t
= 3, then
G
contains a cycle. So
G K
3
. If
t >
3, then
G K
1
+
H
where δ(H) ≥ 2
t−3
. So e(H) ≥ 2
t−4
|H| and (by induction) H K
t−1
.
We can prove similar results for the topological things.
Lemma.
If
δ
(
G
)
≥
2
k
, then
G
contains vertex disjoint subgraphs
H, J
with
δ(H) ≥ k, J connected, and every vertex in H has a neighbour in J.
If we contract J to a single vertex, then we get an H + K
1
.
Proof.
We may assume
G
is connected, or else we can replace
G
by a component.
Now pick a subgraph
J
maximal such that
J
is connected and
e
(
G/J
)
≥
k(|G|− |J| + 1). Note that any vertex could be used for J. So such a J exist.
Let
H
be the subgraph spanned by the vertices having a neighbour in
J
.
Note that if
v ∈ V
(
H
), then
v
has at least
k
neighbours in
H
. Indeed, when we
contract J ∪ {v}, maximality tells us
e(G/(J ∪ {v})) ≤ k(|G| − |J| + 1) − k − 1,
and the number of edges we lose in the contraction is 1 plus the number of
neighbours of
v
(it is easier to think of this as a two-step process — first contract
J
, so that we get an
H
+
K
1
, then contract
v
with the vertex coming from
K
1
).
Again, we iterate this result.
Theorem.
Let
F
be a graph with
n
edges and no isolated vertices. If
δ
(
G
)
≥
2
n
,
then G ⊇ T F .
Proof.
If
n
= 1, then this is immediate. If
F
consists of
n
isolated edges, then
F ⊆ G
(in fact,
δ
(
G
)
≥
2
n −
1 is enough for this). Otherwise, pick an edge
e
which is not isolated. Then
F − e
has at most 1 isolated vertex. Apply the
previous lemma to
G
to obtain
H
with
δ
(
H
)
≥
2
n−1
. Find a copy of
T
(
F − e
)
in H (apart from the isolated vertex, if exists).
If
e
was just a leaf, then just add an edge (say to
J
). If not, just construct a
path going through J to act as e, since J is connected.
It is convenient to make the definition
c(t) = inf{c : e(G) ≥ c|G| ⇒ G K
t
}
t(t) = inf{c : e(G) ≥ c|G| ⇒ G ⊇ T K
t
}.
We can interpret the first result as saying
c
(
t
)
≤
2
t−3
. Moreover, note that if
e
(
G
)
≥ k|G|
, then
G
must contain a subgraph with
δ ≥ k
. Otherwise, we can
keep removing vertices of degree
< k
till we have none left, but still have a
positive number of edges, which is clearly nonsense. Hence, the second result
says t(t) ≤ 2
(
t
2
)
.
Likewise, we can define
f(k) = min{c : κ(G) ≥ c ⇒ G is k-linked}.
Since
κ
(
G
)
≥ c
implies
δ
(
G
)
≥ c
, the existence of
t
(
t
) and the beginning lemma
implies that f (k) exists.
In 1967, Mader showed
c
(
t
) =
t −
2 for
t ≤
7. Indeed, for
t ≤
7, we have the
exact result
ex(n; K
t
) = (t − 2)n −
t − 1
2
.
So for some time, people though c is linear. But in fact, c(t) is superlinear.
Lemma. We have
c(t) ≥ (α + o(1))t
p
log t.
To determine
α
, let
λ <
1 be the root to 1
− λ
+ 2
λ log λ
= 0. In fact
λ ≈
0
.
284.
Then
α =
1 − λ
2
p
log 1/λ
≈ 0.319.
Proof.
Consider a random graph
G
(
n, p
), where
p
is a constant to be chosen
later. So
G
(
n, p
) has
n
vertices and edges are chosen independently at random,
with probability
p
. Here we fix a
t
, and then try to find the best combination of
n and p to give the desired result.
A partition
V
1
, . . . , V
t
of
V
(
G
) is said to be complete if there is an edge
between
V
i
and
V
j
for all
i
and
j
. Note that having a complete partition is a
necessary, but not sufficient condition for having a
K
t
minor. So it suffices to
show that with probability > 0, there is no complete partition.
Writing
q
= 1
−p
, a given partition with
|V
i
|
=
n
i
is complete with probability
Y
i,j
(1 − q
n
i
n
j
) ≤ exp
−
X
i<j
q
n
i
n
j
≤ exp
−
t
2
Y
q
n
i
n
j
/
(
t
2
)
(AM-GM)
≤ exp
−
t
2
q
n
2
/t
2
.
The expected number of complete partitions is then
≤ t
n
exp
−
t
2
q
n
2
/t
2
,
As long as we restrict to the choices of n and q such that
t > n
s
log(1/q)
log n
,
we can bound this by
≤ exp
n log t −
t
2
1
n
= o(1)
in the limit t → ∞. We set
q = λ, n =
t
√
log t
p
log 1/λ
.
Then with probability
>
0, we can find a graph with only
o
(1) many complete
partitions, and by removing o(n) many edges, we have a graph with
p
n
2
− o(n) = (α + o(1))t
p
log t · n
many edges with no K
t
minor.
At this point, the obvious question to ask is — is
t
√
log t
the correct growth
rate? The answer is yes, and perhaps surprisingly, the proof is also probabilistic.
Before we prove that, we need the following lemma:
Lemma.
Let
k ∈ N
and
G
be a graph with
e
(
G
)
≥
11
k|G|
. Then there exists
some H with
|H| ≤ 11k + 2, 2δ(H) ≥ |H|+ 4k − 1
such that G H.
Proof.
We use our previous lemma as a starting point. Letting
`
= 11
k
, we know
that we can find H
1
such that
G K
1
+ H
1
,
with
|H
1
| ≤
2
`
and
δ
(
H
1
)
≥ `
. We shall improve the connectivity of this
H
1
at
the cost of throwing away some elements.
By divine inspiration, consider the constant
β ≈
0
.
37 defined by the equation
1 = β
1 +
log 2
β
,
and the function φ defined by
φ(F ) = β`
|F |
2
log
|F |
β`
+ 1
.
Now consider the set of graphs
C = {F : |F | ≥ β`, e(F ) ≥ φ(F )}.
Observe that H
1
∈ C, since δ(H
1
) ≥ ` and |H
1
| ≤ 2`.
Let H
2
be a subcontraction of H
1
, minimal with respect to C.
Since the complete graph of order
dβ`e
is not in
C
, as
φ >
β`
2
, the only
reason we are minimal is that we have hit the bound on the number of edges.
Thus, we must have
|H
2
| ≥ β` + 1, e(H
2
) = dφ(H
2
)e,
and
e(H
2
/uv) < φ(H
2
/uv)
for all edges uv of H
2
.
Choose a vertex
u ∈ H
2
of minimum degree, and put
H
3
=
H
2
[Γ(
u
)]. Then
we have
|H
3
| = δ(H
2
) ≤
2dφ(H
2
)e
|H
2
|
≤
β`
log
|H
2
|
β`
+ 1
+
2
|H
2
|
≤ `,
since β` ≤ |H
2
| ≤ 2`.
Let’s write b = β` and h = |H
2
|. Then by the usual argument, we have
2δ(H
3
) − |H
3
|
≥ 2(φ(H
2
) − φ(H
2
/uv) − 1) − |H
3
|
≥ bh
log
h
β
+ 1
− b(h − 1)
log
h − 1
b
+ 1
− b
log
h
b
+ 1
− 3
= b(h − 1) log
h
h − 1
− 3
> b − 4,
because h ≥ b + 1 and x log
1 +
1
x
> 1 −
1
x
for real x > 1. So
2δ(H
3
) − |H
3
| ≥ β` − 4 > 4k − 4.
If we put H = K
2
+ H
3
, then G H, |H| ≤ 11k + 2 and
2δ(H) − |H| ≥ 2δ(H
3
) − |H
3
| + 2 ≥ 4k − 1.
Theorem. We have
c(t) ≤ 7t
p
log t
if t is large.
The idea of the proof is as follows: First, we pick some
H
with
G H
such that
H
has high minimum degree, as given by the previous lemma. We
now randomly pick disjoint subsets
U
1
, . . . , U
2t
, and hope that they give us a
subcontraction to
K
t
. There are more sets that we need, because some of them
might be “bad”, in the sense that, for example, there might be no edges from
U
1
to
U
57
. However, since
H
has high minimum degree, the probability of being
bad is quite low, and with positive probability, we can find
t
subsets that have
an edge between any pair. While the
U
i
are not necessarily connected, this is
not a huge problem since
H
has so many edges that we can easily find paths
that connect the different vertices in U
i
.
Proof. For large t, we can choose k ∈ N so that
5.8t
p
log
2
t ≤ 11k ≤ 7t
p
log t.
Let
`
=
d
1
.
01
p
log
2
te
. Then
k ≥ t`/
2. We want to show that
G K
t
if
e(G) ≥ 11k|G|.
We already know that
G H
where
h
=
|H| ≤
11
k
+ 2, and 2
δ
(
H
)
≥
|H|+ 4k − 1. We show that H K
t
.
From now on, we work entirely in
H
. Note that any two adjacent vertices
have
≥
4
k
+1 common neighbours. Randomly select 2
t
disjoint
`
sets
U
1
, . . . , U
2t
in V (H). This is possible since we need 2t` vertices, and 2t` ≤ 4k.
Of course, we only need
t
many of those
`
sets, and we want to select the
ones that have some chance of being useful to us.
Fix a part
U
. For any vertex
v
(not necessarily in
U
), its degree is at least
h/
2. So the probability that
v
has no neighbour in
U
is at most
h/2
`
/
h
`
≤
2
−`
.
Write X(U) for the vertices having no neighbour in U, then E|X(U)| ≤ 2
−`
h.
We say
U
is bad if
|X
(
U
)
| >
8
·
2
−`
h
. Then by Markov’s inequality, the
probability that
U
is bad is
<
1
8
. Hence the expected number of bad sets amongst
U
1
, . . . , U
2t
is
≤
t
4
. By Markov again, the probability that there are more than
t
2
bad sets is <
1
2
.
We say a pair of sets (
U, U
0
) is bad if there is no
U − U
0
edge. Now the
probability that
U, U
0
is bad is
P
(
U
0
⊆ X
(
U
)). If we condition on the event that
U is good (i.e. not bad), then this probability is bounded by
8 · 2
−`
h
`
/
h − `
`
≤ 8
`
2
−`
2
1 +
`
h − `
`
≤ 8
`
2
−`
2
e
`
2
/(h−`)
≤ 9
`
2
−`
2
if
t
is large (hence
`
is slightly large and
h
is very large). We can then bound
this by
1
8t
.
Hence, the expected number of bad pairs (where one of them is good) is at
most
1
8t
2t
2
≤
t
4
.
So the probability that there are more than
t
2
such bad pairs is <
1
2
.
Now with positive probability,
U
1
, . . . , U
2t
has at most
t
2
bad sets and at
most
t
2
bad pairs amongst the good sets. Then we can find
t
many sets that are
pairwise good. We may wlog assume they are U
1
, . . . , U
t
.
Fixing such a choice
U
1
, . . . , U
t
, we now work deterministically. We would
be done if each
U
i
were connected, but they are not in general. However, we
can find
W
1
, . . . , W
t
in
V
(
H
)
\
(
U
1
∪ ···U
t
) such that
U
i
∪ W
i
is connected for
1 ≤ i ≤ t.
Indeed, if
U
i
=
{u
1
, . . . , u
`
}
, we pick a common neighbour of
u
j−1
and
u
j
if
u
j−1
u
j
6∈ E
(
H
), and put it in
W
i
. In total, this requires us to pick
≤ t`
distinct
vertices in
V
(
H
)
−
(
U
1
∪···∪U
t
), and we can do this because
u
j−1
and
u
j
have
at least 4k − t` ≥ t` common neighbours in this set.
It has been shown (2001) that equality holds in the previous lemma.
So we now understand
c
(
t
) quite well. How about subdivision and linking?
We decide to work on
f
(
k
) now, because Robertson and Seymour (1995) showed
that our first lemma that holds if
G T K
3k
instead of
G ⊇ K
3k
. We also know
how many edges we need to get a minor. Combining with our previous theorem,
we know
f(k) = O(k
p
log k).
We know we can’t do better than
k
, but we can get it down to order
k
by proving
our first lemma under the weaker hypothesis that G H where H is dense.
So far, we have proven theorems that say, roughly, “if
G
is a graph with
enough edges, then it subcontracts to some highly connected thing”. Now saying
that
G
subcontracts to some highly connected thing is equivalent to saying we
can find disjoint non-empty connected subgraphs
D
1
, . . . , D
m
such that each
D
i
is connected, and there are many edges between the
D
i
. The lemma we are
going to prove next says under certain conditions, we can choose the
D
i
in a
way that they contain certain prescribed points.
Definition
(
S
-cut)
.
Given
S ⊆ V
(
G
), an
S
-cut is a pair (
A, B
) of subsets of
the vertices such that
A ∪B
=
V
(
G
),
S ⊆ A
and
e
(
A \B, B \A
) = 0. The order
of the cut is |A ∩ B|.
We say (A, B) avoids C if A ∩ V (C) = ∅.
Example. For any S ⊆ A, the pair (A, V (G)) is an S-cut.
Lemma. Let d ≥ 0, k ≥ 2 and h ≥ d + b3k/2c be integers.
Let
G
be a graph,
S
=
{s
1
, . . . , s
k
} ⊆ V
(
G
). Suppose there exists disjoint
subgraphs C
1
, . . . , C
h
of G such that
(∗)
Each
C
i
is either connected, or each of its component meets
S
. Moreover,
each C
i
is adjacent to all but at most d of the C
j
, j 6= i not meeting S.
(†) Moreover, no S-cut of order < k avoids d + 1 of C
1
, . . . , C
h
.
Then G contains disjoint non-empty connected subgraphs D
1
, . . . , D
m
, where
m = h − bk/2c,
such that for 1
≤ i ≤ k
,
s
i
∈ D
i
, and
D
i
is adjacent to all but at most
d
of
D
k+1
, . . . , D
m
.
Proof.
Suppose the theorem is not true. Then there is a minimal counterexample
G (with minimality defined with respect to proper subgraphs).
We first show that we may assume
G
has no isolated vertices. If
v
is an
isolated vertex, and
v 6∈ S
, then we can simply apply the result to
G − v
. If
v ∈ S
, then the
S
-cut (
S, V
(
G
)
\{v}
) of order
k −
1 avoids
h − k ≥ d −
1 of the
C
i
’s.
Claim.
If (
A, B
) is an
S
-cut of order
k
avoiding
d
+ 1 many of the
C
i
’s, then
B = V (G) and A is discrete.
Indeed, given such an S-cut, we define
S
0
= A ∩ B
G
0
= G[B] − E(S
0
)
C
0
i
= C
i
∩ G
0
.
We now make a further claim:
Claim. (G
0
, S
0
, {C
0
i
}) satisfies the hypothesis of the lemma.
We shall assume this claim, and then come back to establishing the claim.
Assuming these claims, we show that
G
isn’t a countrexample after all. Since
(
G
0
, S
0
, {C
0
i
}
) satisfies the hypothesis of the lemma, by minimality, we can find
subgraphs
D
0
1
, . . . , D
0
m
in
G
0
that satisfy the conclusion of the lemma for
G
0
and
S
0
. Of course, these do not necessarily contain our
s
i
Assuming these claims, we
can construct the desired
D
i
. However, we can just add paths from
S
0
to the
s
i
.
Indeed,
G
[
A
] has no
S
-cut (
A
00
, B
00
) of order less than
k
with
S
0
⊆ B
00
, else
(
A
00
, B
00
∪ B
) is an
S
-cut of
G
of the forbidden kind, since
A
, and hence
A
00
avoids too many of the
C
i
. Hence by Menger’s theorem, there are vertex disjoint
paths
P
1
, . . . , P
k
in
G
[
A
] joining
s
i
to
s
0
i
(for some labelling of
S
0
). Then simply
take
D
i
= D
0
i
∪ P
i
.
To check that (
G
0
, S
0
, {C
0
i
}
) satisfy the hypothesis of the lemma, we first
need to show that the C
0
i
are non-empty.
If (
A, B
) avoids
C
j
, then by definition
C
j
∩ A
=
∅
. So
C
j
=
C
0
j
. By
assumption, there are
d
+ 1 many
C
j
’s for which this holds. Also, since these
don’t meet
S
, we know each
C
i
is adjacent to at least one of these
C
j
’s. So in
particular, C
0
i
is non-empty since C
0
i
⊇ C
i
∩ C
0
j
= C
i
∩ C
j
.
Let’s now check the conditions:
(∗)
For each
C
0
i
, consider its components. If there is some component that
does not meet
S
0
, then this component is contained in
B \A
. So this must
also be a component of
C
i
. But
C
i
is connected. So this component is
C
i
.
So C
0
i
= C
i
. Thus, either C
0
i
is connected, or all components meet S
0
.
Moreover, since any
C
0
j
not meeting
S
0
equals
C
j
, it follows that each
C
i
and so each
C
0
i
is adjacent to all but at most
d
of these
C
0
j
s. Therefore (
∗
)
holds.
(†)
If (
A
0
, B
0
) is an
S
0
-cut in
G
0
avoiding some
C
0
i
, then (
A ∪ A
0
, B
0
) is an
S
-cut of
G
of the same order, and it avoids
C
i
(since
C
0
i
doesn’t meet
S
0
,
and we have argued this implies
C
0
i
=
C
i
, and so
C
i
∩A
=
∅
). In particular,
no
S
0
-cut (
A
0
, B
0
) of
G
0
has order less than
k
and still avoids
d
+ 1 of
C
0
1
, . . . , C
0
h
.
We can now use our original claim. We know what
S
-cuts of order
k
loop
like, so we see that if there is an edge that does not join two
C
i
’s, then we
can contract the eedge to get a smaller counterexample. Recalling that
G
has
no isolated vertices, we see that in fact
V
(
G
) =
∪V
(
C
i
), and
|C
i
|
= 1 unless
C
i
⊆ S.
Let
C =
[
{V (C
i
) : |C
i
| ≥ 2}.
We claim that there is a set
I
of
|C|
independent edges meeting
C
. If not, by Hall’s
theorem, we can find
X ⊆ C
whose neighbourhood
Y
(in
V
(
G
)
− S
) such that
|Y | < |X|
. Then (
S ∪Y, V
(
G
)
−X
) is an
S
-cut of order
|S|−|X|
+
|Y | < |S|
=
k
avoiding ≥ |G| − |S| − |Y | many C
i
’s, and this is
≥ |G| − |S|− |X| + 1 ≥ |G| − |C| − k + 1.
But
h ≤ |G| − |C|
+
|C|
2
, since
|G| − |C|
is the number of
C
i
’s of size 1, so we
can bound the above by
≥ h −
|C|
2
− k + 1 ≥ h −
3k
2
+ 1 ≥ d + 1.
This contradiction shows that I exists.
Now we can just write down the D
i
’s. For 1 ≤ i ≤ k, set D
i
to be s
i
if s
i
is
a C
`
with |C
`
| = 1, i.e. s
i
6∈ C. If s
i
∈ C, let D
i
be the edge of I meeting S
i
.
Let
D
k+1
, . . . , D
m
each be single vertices of
G − S −
(
ends of I
). Note those
exist because
≥ |G| − k − |C| ≥ h − b
3k
2
c
=
m − k
vertices are avaiable. Note
that each
D
i
contains a
C
`
with
|C
`
|
= 1. So each
D
i
is joined to all but
≤ d
many D
j
’s.
The point of this result is to prove the following theorem:
Theorem.
Let
G
be a graph with
κ
(
G
)
≥
2
k
and
e
(
G
)
≥
11
k|G|
. Then
G
is
k-linked. In particular, f(k) ≤ 22k.
Note that if κ(G) ≥ 22k then δ(G) ≥ 22k, so e(G) ≥ 11k|G|.
Proof.
We know that under these conditions,
G H
with
|H| ≤
11
k
+ 2 and
2δ(H) ≥ |H|+ 4k − 1. Let h = |H|, and d = h − 1 − δ(H). Note that
h = 2d − 2 + 2δ(H) − h ≥ 2d + 4k.
Let
C
1
, . . . , C
k
be connected subgraphs of
G
which contract to form
H
. Then
clearly each
C
i
is joined to all but at most
h −
1
− δ
(
H
) =
d
other
C
j
’s.
Now let
s
1
, . . . , s
k
, t
1
, . . . , t
k
be the vertices we want to link up. Let
S
=
{s
1
, . . . , s
k
, t
1
, . . . , t
k
}
. Observe that
G
has no
S
-cut of order
<
2
k
at all since
κ(G) ≥ 2k. So the conditions are satisfied, but with 2k instead of k.
So there are subgraphs
D
1
, . . . , D
m
, where
m
=
h −k ≥
2
d
+ 3
k
as described.
We may assume
s
i
∈ D
i
and
t
i
∈ D
k+i
. Note that for each pair (
D
i
, D
j
), we can
find
≥ m −
2
d ≥
3
k
other
D
`
such that
D
`
is joined to both
D
i
and
D
j
. So for
each
i
= 1
, . . . , k
, we can find an unused
D
`
not among
D
1
, . . . , D
2k
that we can
use to connect up D
i
and D
k+i
, hence s
i
and t
i
.
In 2004, the coefficient was reduced from 11 to 5. This shows
f
(
k
)
≤
10
k
. It
is known that f(1) = 3, f(2) = 6 and f(k) ≥ 3k − 2 for k ≥ 3.
Finally, we consider the function
t
(
t
). We begin by the following trivial
lemma:
Lemma. If δ(a) ≥ t
2
and G is
t+2
3
-linked, then G ⊇ T K
t
.
Proof.
Since
δ
(
G
)
≥ t
2
, we may pick vertices
v
1
, . . . , v
t
and sets
U
1
, . . . U
t
all
disjoint so that
|U
i
|
=
t −
1 and
v
i
is joined to
U
i
. Then
G − {v
1
, . . . , v
k
}
is still
t+2
2
−t
=
t
2
-linked. So
U
1
, . . . , U
t−1
may be joined with paths to form a
T K
t
in G.
To apply our previous theorem together with this lemma, we need the
following lemma:
Lemma.
Let
k, d ∈ N
with
k ≤
d+1
2
, and suppose
e
(
G
)
≥ d|G|
. Then
G
contains
a subgraph H with
e(H) = d|H| − kd + 1, δ(H) ≥ d + 1, κ(H) ≥ k.
Proof. Define
E
d,k
= {F ⊆ G : |F | ≥ d, e(F ) > d|F | − kd}.
We observe that
D ∈ E
d,k
, but
K
d
6∈ E
d,k
. Hence
|F | > d
for all
F ∈ E
d,k
. let
H
be a subgraph of
G
minimal with respect to
H ∈ E
d,k
. Then
e
(
H
) =
d|H|−kd
+1,
and δ(H) ≥ d + 1, else H − v ∈ E
d,k
for some v ∈ H.
We only have to worry about the connectivity condition. Suppose
S
is a
cutset of
H
. Let
C
be a component of
G − S
. Since
δ
(
h
)
≥ d
+ 1, we have
|C ∪ S| ≥ d + 2 and |H − C| ≥ d + 2.
Since neither C sup S nor H − C lies in that class, we have
e(C ∪ S) ≤ d|C ∪ S| − kd ≤ d|C| + d|S| − kd
and
e(H − C) ≤ d|H| − d|C|− kd.
So we find that
e(H) ≤ d|H| + d|S| − 2kd.
But we know this is equal to d|H|− kd + 1. So we must have |S| ≥ k.
Theorem.
t
2
16
≤ t(t) ≤ 13
t + 1
2
.
Recall our previous upper bound was something like 2
t
2
. So this is an
improvement.
Proof.
The lower bound comes from (disjoint copies of)
K
t
2
/8,t
2
/8
. For the
uppper bound, write
d = 13
t + 1
2
, k = t · (t + 1).
Then we can find a subgraph H with δ(H) ≥ d + 1 and κ(H) ≥ k + 1.
Certainly |H| ≥ d + 2, and we know
e(H) ≥ d|H| − kd > (d − k)|H| ≥ 11
t + 1
2
|H|.
So we know H is
t+1
2
-linked, and so H ⊇ T K
t
.
So t(t) is, more or less, t
2
!
6 Extremal hypergraphs
Define
K
`
`
(
t
) be the complete
`
-partite
`
-uniform hypergraph with
`
classes of
size t, containing all t
`
edges with one vertex in each class.
Theorem
(Erd¨os)
.
Let
G
be
`
-uniform of order
n
with
p
n
`
edges, where
p ≥ 2n
−1/t
`−1
. Then G contains K
`
`
(t) (provided n is large).
If we take
`
= 2, then this agrees with what we know about the exact value
of the extremal function.
Proof.
Assume that
t ≥
2. We proceed by induction on
` ≥
2. For each (
`−
1)-set
σ ⊆ V (G), let
N(σ) = {v : σ ∪ {v} ∈ E(G)}.
Then the average degree is
n
` − 1
−1
X
|N(σ)| =
n
` − 1
−1
`|E(G)| = p(n − ` + 1).
For each of the
n
t
many t-sets T ⊆ V (G), let
D(T) = {σ : T ⊆ N(σ)}.
Then
X
T
|D(T)| =
X
σ
|N(σ)|
t
≥
n
` − 1
p(n − ` + 1)
t
,
where the inequality follows from convexity, since we can assume that
p
(
n − `
+
1) ≥ t − 1 if n is large.
In particular, there exists a T with
|D(T)| ≥
n
t
−1
n
` − 1
p(n − ` + 1)
t
≥
1
2
p
t
n
` − 1
.
when n is large. By our choice of t, we can write this as
|D(T)| ≥ 2
t−1
n
−1/t
`−2
n
` − 1
.
If ` = 2, then this is ≥ 2
t−1
≥ t. So T is joined to a T -set giving K
t,t
.
If
` ≥
3, then
|D
(
T
)
| ≥
2
n
−1/t
`−2
n
`−1
. So, by induction, the (
` −
1)-uniform
hypergraph induced by the
σ
with
T ⊆ N
(
σ
) contains
K
`−1
`−1
(
t
), giving
K
`
`
(
t
)
with T .
We can do a simple random argument to show that this is a right-order of
magnitude.