1Graph Ramsey theory
III Ramsey Theory
1.2 Finite graphs
We now move on to discuss a finitary version of the above problem. Of course, if
we finitely colour an infinite graph, then we can obtain a finite monochromatic
subgraph of any size we want, because this is just a much weaker version of
Ramsey’s theorem. However, given
n < N
, if we finitely colour a graph of size
N, are we guaranteed to have a monochromatic subgraph of size n?
Before we begin, we note some definitions. Recall again that a graph
G
is a
pair (V, E) where E ⊆ V
(2)
.
Example. The path graph on n vertices P
n
is
We can write
V = [n], E = {12, 23, 34, ··· , (n − 1)n}.
Example. The n-cycle C
n
is
V = [n], E = {12, 23, ··· , (n − 1)n, 1n}.
Finally, we have
Example. The complete graph V
n
on n vertices is
V = [n], E = V
(2)
.
Concretely, the question we want to answer is the following — how big
does our (complete) graph have to be to guarantee a complete monochromatic
subgraph of size n?
In this section, we will usually restrict to 2 colours. Everything we say will
either be trivially be generalizable to more colours, or we have no idea how to
do so. It is an exercise for the reader to figure out which it is.
Definition
(Ramsey number)
.
We let
R
(
n
) =
R
(
K
n
) to be the smallest
N ∈ N
whenever we red-blue colour the edges of
K
N
, then there is a monochromatic
copy of K
n
.
It is not immediately obvious that
R
(
n
) has to exist, i.e. it is a finite number.
It turns out we can easily prove this from the infinite Ramsey theorem.
Theorem (Finite Ramsey theorem). For all n, we have R(n) < ∞.
Proof.
Suppose not. Let
n
be such that
R
(
n
) =
∞
. Then for any
m ≥ n
, there
is a 2-colouring
c
m
of
K
m
= [
m
]
(2)
such that there is no monochromatic set of
size n.
We want to use these colourings to build up a colouring of
N
(2)
with no
monochromatic set of size
n
. We want to say we take the “limit” of these
colourings, but what does this mean? To do so, we need these colourings to be
nested.
By the pigeonhole principle, there exists an infinite set
M
1
⊆ N
and some
fixed 2-colouring d
n
of [n] such that c
m
|
[n]
(2)
= d
n
for all m ∈ M
1
.
Similarly, there exists an infinite
M
2
⊆ M
1
such that
c
m
|
[n+1]
(2)
=
d
n+1
for
m ∈ M
2
, again for some 2-colouring
d
n+1
of [
n
+ 1]. We repeat this over and
over again. Then we get a sequence
d
n
, d
n+1
, ···
of colourings such that
d
i
is a
2-colouring of [
i
]
(2)
without a monochromatic
K
n
, and further for
i < j
, we have
d
j
|
[i]
(2)
= d
i
.
We then define a 2-colouring c of N
(2)
by
c(ij) = d
m
(ij)
for any m > i, j. Clearly, there exists no monochromatic K
n
in c, as any K
n
is
finite. This massively contradicts the infinite Ramsey theorem.
There are other ways of obtaining the finite Ramsey theorem from the infinite
one. For example, we can use the compactness theorem for first order logic.
Proof.
Suppose
R
(
n
) =
∞
. Consider the theory with proposition letters
p
ij
for
each
ij ∈ N
(2)
. We will think of the edge
ij
as red if
p
ij
=
>
, and blue if
p
ij
=
⊥
.
For each subset of
N
of size
n
, we add in the axiom that says that set is not
monochromatic.
Then given any finite subset of the axioms, it mentions only finitely many
subsets of
N
. Suppose it mentions vertices only up to
m ∈ N
. Then by assumption,
there is a 2-colouring of [
m
]
(2)
with no monochromatic subset of size
n
. So by
assigning
p
ij
accordingly (and randomly assigning the remaining ones), we have
found a model of this finite subtheory. Thus every finite fragment of the theory
is consistent. Hence the original theory is consistent. So there is a model, i.e. a
colouring of N
(2)
with no monochromatic subset.
This contradicts the infinite Ramsey theorem.
Similarly, we can do it by compactness of the space
{
1
,
2
}
N
endowed with
metric
d(f, g) =
1
2
n
if n = min{i : f
i
6= g
i
}.
By Tychonoff theorem, we know this is compact, and we can deduce the theorem
from this.
While these theorems save work by reusing the infinite Ramsey theorem, it
is highly non-constructive. It is useless if we want to obtain an actual bound on
R
(
n
). We now go back and see what we did when we proved the infinite Ramsey
theorem.
To prove the infinite Ramsey theory, We randomly picked a point
a
1
. Then
there are some things that are connected by red to it, and others connected by
blue:
a
1
Next we randomly pick a point in one of the red or blue sets, and try to move on
from there. Suppose we landed in the red one. Now note that if we find a blue
K
n
in the red set, then we are done. But on the other hand, we only need a red
K
n−1
, and not a full blown
K
n
. When we moved to this red set, the problem is
no longer symmetric.
Thus, to figure out a good bound, it is natural to consider an asymmetric
version of the problem.
Definition
(Off-diagonal Ramsey number)
.
We define
R
(
n, m
) =
R
(
K
n
, K
m
)
to be the minimum
N ∈ N
such that whenever we red-blue colour the edges of
K
N
, we either get a red K
n
or a blue K
m
.
Clearly we have
R(n, m) ≤ R(max{n, m}).
In particular, they are finite. Once we make this definition, it is easy to find a
bound on R.
Theorem. We have
R(n, m) ≤ R(n − 1, m) + R(n, m − 1).
for all n, m ∈ N. Consequently, we have
R(n, m) ≤
n + m −1
n − 2
.
Proof. We induct on n + m. It is clear that
R(1, n) = R(n, 1) = 1, R(n, 2) = R(2, n) = n
Now suppose
N ≥ R
(
n −
1
, m
) +
R
(
n, m −
1). Consider any red-blue colouring
of K
N
and any vertex v ∈ V (K
n
). We write
v(K
n
) \ {v} = A ∪ B,
where each vertex
A
is joined by a red edge to
v
, and each vertex in
B
is joined
by a blue edge to v. Then
|A| + |B| ≥ N − 1 ≥ R(n − 1, m) + R(n, m − 1) − 1.
It follows that either
|A| ≥ R
(
n −
1
, m
) or
|B| ≥ R
(
n, m −
1). We wlog it is the
former. Then by definition of
R
(
n −
1
, m
), we know
A
contains either a blue
copy of
K
m
or a red copy of
K
n−1
. In the first case, we are done, and in the
second case, we just add v to the red K
n−1
.
The last formula is just a straightforward property of binomial coefficients.
In particular, we find
R(n) ≤
2n − 1
n − 2
≤
4
n
√
n
.
We genuinely have no idea whether
∼
4
n
is the correct growth rate, i.e. if there
is some
ε
such that
R
(
n
)
≤
(4
− ε
)
n
. However, we do know that for any
c >
0,
we eventually have
R(n) ≤
4
n
n
c
.
That was an upper bound. Do we have a lower bound? In particular, does
R
(
n
)
have to grow exponentially? The answer is yes, and the answer is a very classical
construction of Erd¨os.
Theorem. We have R(n) ≥
√
2
n
for sufficiently large n ∈ N.
The proof is remarkable in that before this was shown, we had no sensible
bound at all. However, the proof is incredibly simple, and revolutionized how
we think about colourings.
Proof.
Let
N ≤
√
2
n
. We perform a red-blue colouring of
K
N
randomly, where
each edge is coloured red independently of the others with probability
1
2
.
We let
X
R
be the number of red copies of
K
n
in such a colouring. Then
since expectation is linear, we know the expected value is
[X
R
] =
N
n
1
2
(
n
2
)
≤
eN
n
n
1
2
(
n
2
)
≤
e
n
n
√
2
n
2
√
2
−n
2
=
e
n
n
<
1
2
for sufficiently large n.
Similarly, we have [
X
B
]
<
1
2
. So the expected number of monochromatic
K
n
is
<
1. So in particular there must be some colouring with no monochromatic
K
n
.
Recall the bound
R(m, n) ≤
m + n −2
m − 1
.
If we think of m as being fixed, then this tells us
R(m, n) ∼ (n + m)
m−1
.
For example, if m is 3, then we have
R(3, n) ≤
n + 1
2
=
n(n + 1)
2
∼ n
2
.
We can sort-of imagine where this bound came from. Suppose we randomly pick
a vertex
v
1
. Then if it is connected to at least
n
other vertices by a red edge,
then we are done — if there is even one red edge among those
n
things, then we
have a red triangle. Otherwise, all edges are blue, and we’ve found a complete
blue K
n
.
So this is connected to at most
n −
1 things by a red edge. So if our graph
is big enough, we can pick some
v
2
connected to
v
1
by a blue edge, and do the
same thing to
v
2
. We keep going on, and by the time we reach
v
n
, we would
have found
v
1
, ··· , v
n
all connected to each other by blue edges, and we are
done. So we have K(3, n) ∼ n
2
.
v
1
v
2
v
3
But this argument is rather weak, because we didn’t use that large pool of blue
edges we’ve found at v
1
. So in fact this time we can do better than n
2
.
Theorem. We have
R(3, n) ≤
100n
2
log n
for sufficiently large n ∈ N.
Here the 100 is, obviously, just some random big number.
Proof.
Let
N ≥
100
n
2
/ log n
, and consider a red-blue colouring of the edges of
K
N
with no red K
3
. We want to find a blue K
n
in such a colouring.
We may assume that
(i) No vertex v has ≥ n red edges incident to it, as argued just now.
(ii) If we have v
1
, v
2
, v
3
such that v
1
v
2
and v
1
v
3
are red, then v
2
v
3
is blue:
v
1
v
2
v
3
We now let
F = {W : W ⊆ V (K
N
) such that W
(2)
is monochromatic and blue}.
We want to find some
W ∈ F
such that
|W | ≥ n
, i.e. a blue
K
n
. How can we
go about finding this?
Let
W
be a uniformly random member of
F
. We will be done if we can show
that that E[|W |] ≥ n.
We are going to define a bunch of random variables. For each vertex
v ∈
V (K
N
), we define the variable
X
v
= n1
{v∈W }
+ |{u : uv is red and u ∈ W }|.
Claim.
E[X
v
] >
log n
10
for each vertex v.
To see this, let
A = {u : uv is red}
and let
B = {u : uv is blue}.
then from the properties we’ve noted down, we know that
|A| < n
and
A
(2)
is
blue. So we know very well what is happening in
A
, and nothing about what is
in B.
We fix a set
S ⊆ B
such that
S ∈ F
, i.e.
S
(2)
is blue. What can we say about
W if we condition on B ∩ W = S?
a
1
S
B
A
T
Let
T ⊆ A
be the set of vertices that are joined to
S
only by blue edges. Write
|T |
=
x
. Then if
B ∩W
=
S
, then either
W ⊆ S ∪T
, or
W ⊆ S ∪{v}
. So there
are exactly 2
x
+ 1 choices of W . So we know
E[X
v
| W ∩ B = S] ≥
n
2
x
+ 1
+
2
x
2
x
+ 1
(E[|random subset of T|])
=
n
2
x
+ 1
+
2
x−1
x
2
x
+ 1
.
Now if
x <
log n
2
,
then
n
2
x
+ 1
≥
n
√
n + 1
≥
log n
10
for all sufficiently large n. On the other hand, if
x ≥
log n
2
,
then
2
x−1
x
2
x
+ 1
≥
1
4
·
log n
2
≥
log n
10
.
So we are done.
Claim.
X
v∈V
X
v
≤ 2n|W |.
To see this, for each vertex
v
, we know that if
v ∈ W
, then it contributes
n
to the sum via the first term. Also, by our initial observation, we know that
v ∈ W
has at most
n
neighbours. So it contributes at most
n
to the second term
(acting as the “u”).
Finally, we know that
E[|W |] ≥
1
2n
X
E[X
V
] ≥
N
2n
log n
10
≥
100n
2
log n
·
log n
20n
≥ 5n.
Therefore we can always find some W ∈ F such that |W | ≥ n.
Now of course, there is the following obvious generalization of Ramsey
numbers:
Definition
(
R
(
G, H
))
.
Let
G, H
be graphs. Then we define
R
(
G, H
) to be the
smallest
N
such that any red-blue colouring of
K
N
has either a red copy of
G
or a blue copy of H.
Obviously, we have
R
(
G, H
)
≤ R
(
|G|, |H|
). So the natural question is if we
can do better than that.
Exercise. Show that
R(P
n
, P
n
) ≤ 2n.
So sometimes it can be much better.