2Stability
III Extremal Graph Theory
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).