1The Erdos–Stone theorem
III Extremal Graph Theory
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.