1Graph Ramsey theory

III Ramsey Theory



1.1 Infinite graphs
We begin by laying out some notations and definitions.
Definition (N and [n]). We write
N = {1, 2, 3, 4, ···}.
We also write
[n] = {1, 2, 3, ··· , n}.
Notation.
For a set
X
, we write
X
(r)
for the subsets of
X
of size
r
. The
elements are known as r-sets.
We all know what a graph is, hopefully, but for concreteness we provide a
definition:
Definition (Graph). A graph G is a pair (V, E), where E V
(2)
.
In particular, our graphs are not directed.
We are mostly interested in graphs with
V
=
N
or [
n
]. In this case, we will
write an edge
{i, j}
as
ij
, and always assume that
i < j
. More generally, in
N
(r)
,
we write i
1
i
2
···i
r
for an r-set, and implicitly assume i
1
< i
2
< ··· < i
r
.
Definition (k-colouring). A k-colouring of a set X is a map c : X [k].
Of course, we often replace
k
with some actual set of colours, e.g.
{red, blue}
.
We make more obvious definitions:
Definition
(Monochromatic set)
.
Let
X
be a set with a
k
-colouring. We say a
subset Y X is monochromatic if the colouring restricted to Y is constant.
The first question we are interested is in the following — if
N
(2)
is
k
-coloured,
can we find a complete infinite subgraph that is monochromatic? In other words,
is there an infinite subset X N such that X
(2)
N
(2)
is monochromatic?
We begin by trying some examples. The correct way to read these examples
is to stare at the colouring, and then try to find a monochromatic subset yourself,
instead of immediately reading on to see what the monochromatic subset is.
Example. Suppose we had the colouring c : N
(2)
{red, blue} by
c(ij) =
(
red i + j is even
blue i + j is odd
.
Then we can pick
X
=
{
2
,
4
,
6
,
8
, ···}
, and this is an infinite monochromatic set.
Example. Consider c : N
(2)
{0, 1, 2}, where
c(ij) = max{n : 2
n
| i + j} mod 3
In this case, taking
X
=
{
8
,
8
2
,
8
3
, ···}
gives an infinite monochromatic set of
colour 0.
Example. Let c : N
(2)
{red, blue} by
c(ij) =
(
red i + j has an even number of distinct prime factors
blue otherwise
It is in fact an open problem to find an explicit infinite monochromatic set
for this colouring, or even for which colour do we have an infinite monochromatic
set. However, we can prove that such a set must exist!
Theorem
(Ramsey’s theorem)
.
Whenever we
k
-colour
N
(2)
, there exists an
infinite monochromatic set
X
, i.e. given any map
c
:
N
(2)
[
k
], there exists a
subset X N such that X is infinite and c|
X
(2)
is a constant function.
Proof.
Pick an arbitrary point
a
1
N
. Then by the pigeonhole principle, there
must exist an infinite set
B
1
N \ {a
1
}
such that all the
a
1
-
B
1
edges (i.e. edges
of the form (a
1
, b
1
) with b
1
B
1
) are of the same colour c
1
.
Now again arbitrarily pick an element
a
2
B
1
. Again, we find some infinite
B
2
B
1
such that all
a
2
-
B
2
edges are the same colour
c
2
. We proceed inductively.
a
1
a
2
We obtain a sequence
{a
1
, a
2
, ···}
and a sequence of colours
{c
1
, c
2
, ···}
such
that c(a
i
, a
j
) = c
i
, for i < j.
Now again by the pigeonhole principle, since there are finitely many colours,
there exists an infinite subsequence
c
i
1
, c
i
2
, ···
that is constant. Then
a
i
1
, a
i
2
, ···
is an infinite monochromatic set, since all edges are of the colour
c
i
1
=
c
i
2
=
···
.
So we are done.
This proof exhibits many common themes we will see in the different Ram-
sey theory proofs we will later do. The first is that the proof is highly non-
constructive. Not only does it not give us the infinite monochromatic set; it
doesn’t even tell us what the colour is.
Another feature of the proof is that we did not obtain the infinite monochro-
matic set in one go. Instead, we had to first pass through that intermediate
structure, and then obtain an infinite monochromatic set from that. In future
proofs, we might have to go through many passes, instead of just two.
This theorem looks rather innocuous, but it has many interesting applications.
Corollary
(Bolzano-Weierstrass theorem)
.
Let (
x
i
)
i0
be a bounded sequence
of real numbers. Then it has a convergent subsequence.
Proof. We define a colouring c : N
(2)
{↑, ↓}, where
c(ij) =
(
x
i
< x
j
x
j
x
i
Then Ramsey’s theorem gives us an infinite monochromatic set, which is the
same as a monotone subsequence. Since this is bounded, it must convergence.
With a very similar technique, we can prove that we can do this for
N
(r)
for
any r, and not just N
(2)
.
Theorem
(Ramsey’s theorem for
r
sets)
.
Whenever
N
(r)
is
k
-coloured, there
exists an infinite monochromatic set, i.e. for any
c
:
N
(r)
[
k
], there exists an
infinite X N such that c|
X
(r)
is constant.
We can again try some concrete examples:
Example. We define c : N
(3)
{red, blue} by
c(ijk) =
(
red i | j + k
blue otherwise
Then X = {2
0
, 2
1
, 2
2
, ···} is an infinite monochromatic set.
Proof.
We induct on
r
. This is trivial when
r
= 1. Assume
r >
1. We fix
a
1
N
.
We induce a k-colouring c
1
of (N \ {a
1
})
(r1)
by
c
1
(F ) = c(F {a
1
}).
By induction, there exists an infinite
B
1
N\{a
1
}
such that
B
1
is monochromatic
for c
1
, i.e. all a
1
-B
1
r-sets have the same colour c
1
.
We proceed inductively as before. We get
a
1
, a
2
, a
3
, ···
and colours
c
1
, c
2
, ···
etc. such that for any
r
-set
F
contained in
{a
1
, a
2
, ···}
, we have
c
(
F
) =
c
min F
.
Then again, there exists
c
i
1
, c
i
2
, c
i
3
, ···
all identical, and our monochromatic
set is {a
i
1
, a
i
2
, a
i
3
, ···}.
Now a natural question to ask is what happens when we have infinitely
many colours? Clearly an infinite monochromatic subset cannot be guaranteed,
because we can just colour all edges with different colours.
The natural compromise is to ask if we can find an
X
such that either
c|
X
is
monochromatic, or
c|
X
is injective. After a little thought, we realize this is also
impossible. We can construct a colouring on
N
(2)
as follows: we first colour all
edges that involve 1 with the colour 1, then all edges that involve 2 with the
colour 2 etc:
. . .
It is easy to see that we cannot find an infinite monochromatic subset or an
infinite subset with all edges of different colours.
However, this counterexample we came up with still has a high amount of
structure the colour of the edges are uniquely determined by the first element.
It turns out this is the only missing piece (plus the obvious dual case).
With this, we can answer our previous question:
Theorem
(Canonical Ramsey theorem)
.
For any
c
:
N
(2)
N
, there exists an
infinite X N such that one of the following hold:
(i) c|
X
(2)
is constant.
(ii) c|
X
(2)
is injective.
(iii) c(ij) = c(k`) iff i = k for all i, j, k, ` X.
(iv) c(ij) = c(k`) iff j = ` for all i, j, k, ` X.
Recall that when we write
ij
, we always implicitly assume
i < j
, so that (iii)
and (iv) make sense.
In previous proofs, we only had to go through two passes to get the desired
set. This time we will need more.
Proof. Consider the following colouring of X
(4)
: let c
1
be a 2-colouring
c
1
(ijk`) =
(
SAME c(ij) = c(k`)
DIFF otherwise
Then we know there is some infinite monochromatic set
X
1
N
for
c
1
. If
X
1
is
coloured
SAME
, then we are done. Indeed, for any pair
ij
and
i
0
j
0
in
X
1
, we can
pick some huge k, ` such that j, j
0
< k < `, and then
c(ij) = c(k`) = c(i
0
j
0
)
as we know c
1
(ijk`) = c
1
(i
0
j
0
k`) = SAME.
What if
X
1
is coloured
DIFF
? We next look at what happens when we have
edges that are nested each other. We define
c
2
:
X
(4)
1
{SAME, DIFF}
defined by
c
2
(ijk`) =
(
SAME c(i`) = c(jk)
DIFF otherwise
Again, we can find an infinite monochromatic subset
X
2
X
1
with respect to
c
2
.
We now note that
X
2
cannot be coloured
SAME
. Indeed, we can just look at
i j
k `
m n
So if X
2
were SAME, we would have
c(`m) = c(in) = c(jk),
which is impossible since X
1
is coloured DIFF under c
1
.
So X
2
is DIFF. Now consider c
3
: X
(4)
2
{SAME, DIFF} given by
c
3
(ijk`) =
(
SAME c(ik) = c(j`)
DIFF otherwise
Again find an infinite monochromatic subset
X
3
X
2
for
c
3
. Then
X
3
cannot
be SAME, this time using the following picture:
contradicting the fact that c
2
is DIFF. So we know X
3
is DIFF.
We have now have ended up in this set
X
3
such that if we have any two pairs
of edges with different end points, then they must be different.
We now want to look at cases where things share a vertex. Consider
c
4
:
X
(3)
3
{SAME, DIFF} given by
c
4
(ijk) =
(
SAME c(ij) = c(jk)
DIFF otherwise
Let
X
4
X
3
be an infinite monochromatic set for
c
4
. Now
X
4
cannot be
coloured SAME, using the following picture:
which contradicts the fact that
c
1
is
DIFF
. So we know
X
4
is also coloured
DIFF
under c
4
.
We are almost there. We need to deal with edges that nest in the sense of
(iii) and (iv). We look at c
5
: X
(3)
4
{LSAME, LDIFF} given by
c
5
(ijk) =
(
LSAME c(ij) = c(ik)
LDIFF otherwise
Again we find
X
5
X
4
, an infinite monochromatic set for
c
5
. We don’t separate
into cases yet, because we know both cases are possible, but move on to classify
the right case as well. Define c
6
: X
(3)
5
{RSAME, RDIFF} given by
c
5
(ijk) =
(
RSAME c(ik) = c(jk)
RDIFF otherwise
Let X
6
X
5
be an infinite monochromatic subset under c
5
.
As before, we can check that it is impossible to get both
LSAME
and
RSAME
,
using the following picture:
contradicting c
4
being DIFF.
Then the remaining cases (
LDIFF, RDIFF
), (
LSAME, RDIFF
) and (
RDIFF, LSAME
)
corresponds to the cases (ii), (iii) and (iv).
Note that we could this theorem in one pass only, instead of six, by considering
a much more complicated colouring (c
1
, c
2
, c
3
, c
4
, c
5
, c
6
) with values in
{SAME, DIFF}
4
× {LSAME, LDIFF} × {RSAME, RDIFF},
but we still have to do the same analysis and it just complicates matters more.
There is a generalization of this to
r
-sets. One way we can rewrite the
theorem is to say that the colour is uniquely determined by some subset of the
vertices. The cases (i), (ii), (iii), (iv) correspond to no vertices, all vertices, first
vertex, and second vertex respectively. Then for
r
-sets, we have 2
r
possibilities,
one for each subset of the r-coordinates.
Theorem
(Higher dimensional canonical Ramsey theorem)
.
Let
c
:
N
(r)
N
be a colouring. Then there exists
D
[
r
] and an infinite subset
X N
such
that for all
x, y X
(r)
, we have
c
(
x
) =
c
(
y
) if
{i
:
x
i
=
y
i
} D
, where
x = {x
1
< x
2
< ··· < x
r
} (and similarly for y).