III Ramsey Theory - Graph Ramsey theory

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

, we write

(r)

for the subsets of

of size

. 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

or [

]. In this case, we will

write an edge

{i, j}

, and always assume that

i < j

. More generally, in

(r)

we write i

···i

for an r-set, and implicitly assume i

< i

< ··· < i

Definition (k-colouring). A k-colouring of a set X is a map c : X → [k].

Of course, we often replace

with some actual set of colours, e.g.

{red, blue}

We make more obvious definitions:

Definition

(Monochromatic set)

Let

be a set with a

-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

(2)

-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

{

, ···}

, and this is an infinite monochromatic set.

Example. Consider c : N

(2)

→ {0, 1, 2}, where

c(ij) = max{n : 2

| i + j} mod 3

In this case, taking

{

, ···}

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

-colour

(2)

, there exists an

infinite monochromatic set

, i.e. given any map

(2)

→

[

], there exists a

subset X ⊆ N such that X is infinite and c|

(2)

is a constant function.

Proof.

Pick an arbitrary point

∈ N

. Then by the pigeonhole principle, there

must exist an infinite set

⊆ N \ {a

}

such that all the

edges (i.e. edges

of the form (a

, b

) with b

∈ B

) are of the same colour c

Now again arbitrarily pick an element

∈ B

. Again, we find some infinite

⊆ B

such that all

edges are the same colour

. We proceed inductively.

We obtain a sequence

, a

, ···}

and a sequence of colours

, c

, ···}

such

that c(a

, a

) = c

, for i < j.

Now again by the pigeonhole principle, since there are finitely many colours,

there exists an infinite subsequence

, c

, ···

that is constant. Then

, a

, ···

is an infinite monochromatic set, since all edges are of the colour

···

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 (

)

i≥0

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

< x

↓ x

≤ x

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

(r)

for

any r, and not just N

(2)

Theorem

(Ramsey’s theorem for

sets)

Whenever

(r)

-coloured, there

exists an infinite monochromatic set, i.e. for any

(r)

→

[

], there exists an

infinite X ⊆ N such that c|

(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

, 2

, ···} is an infinite monochromatic set.

Proof.

We induct on

. This is trivial when

= 1. Assume

r >

1. We fix

∈ N

We induce a k-colouring c

of (N \ {a

})

(r−1)

(F ) = c(F ∪{a

}).

By induction, there exists an infinite

⊆ N\{a

}

such that

is monochromatic

for c

, i.e. all a

-B

r-sets have the same colour c

We proceed inductively as before. We get

, a

, ···

and colours

, c

, ···

etc. such that for any

-set

contained in

, a

, ···}

, we have

(

) =

min F

Then again, there exists

, c

, ···

all identical, and our monochromatic

set is {a

, a

, ···}.

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

such that either

monochromatic, or

is injective. After a little thought, we realize this is also

impossible. We can construct a colouring on

(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

(2)

→ N

, there exists an

infinite X ⊆ N such that one of the following hold:

(i) c|

(2)

is constant.

(ii) c|

(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

, 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

be a 2-colouring

(ijk`) =

(

SAME c(ij) = c(k`)

DIFF otherwise

Then we know there is some infinite monochromatic set

⊆ N

for

. If

coloured

SAME

, then we are done. Indeed, for any pair

and

, we can

pick some huge k, ` such that j, j

< k < `, and then

c(ij) = c(k`) = c(i

)

as we know c

(ijk`) = c

k`) = SAME.

What if

is coloured

DIFF

? We next look at what happens when we have

edges that are nested each other. We define

(4)

→ {SAME, DIFF}

defined by

(ijk`) =

(

SAME c(i`) = c(jk)

DIFF otherwise

Again, we can find an infinite monochromatic subset

⊆ X

with respect to

We now note that

cannot be coloured

SAME

. Indeed, we can just look at

i j

k `

m n

So if X

were SAME, we would have

c(`m) = c(in) = c(jk),

which is impossible since X

is coloured DIFF under c

So X

is DIFF. Now consider c

: X

(4)

→ {SAME, DIFF} given by

(ijk`) =

(

SAME c(ik) = c(j`)

DIFF otherwise

Again find an infinite monochromatic subset

⊆ X

for

. Then

cannot

be SAME, this time using the following picture:

contradicting the fact that c

is DIFF. So we know X

is DIFF.

We have now have ended up in this set

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

(3)

→ {SAME, DIFF} given by

(ijk) =

(

SAME c(ij) = c(jk)

DIFF otherwise

Let

⊆ X

be an infinite monochromatic set for

. Now

cannot be

coloured SAME, using the following picture:

which contradicts the fact that

DIFF

. So we know

is also coloured

DIFF

under c

We are almost there. We need to deal with edges that nest in the sense of

(iii) and (iv). We look at c

: X

(3)

→ {LSAME, LDIFF} given by

(ijk) =

(

LSAME c(ij) = c(ik)

LDIFF otherwise

Again we find

⊆ X

, an infinite monochromatic set for

. 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

: X

(3)

→ {RSAME, RDIFF} given by

(ijk) =

(

RSAME c(ik) = c(jk)

RDIFF otherwise

Let X

⊆ X

be an infinite monochromatic subset under c

As before, we can check that it is impossible to get both

LSAME

and

RSAME

using the following picture:

contradicting c

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

, c

) with values in

{SAME, DIFF}

× {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

-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

-sets, we have 2

possibilities,

one for each subset of the r-coordinates.

Theorem

(Higher dimensional canonical Ramsey theorem)

Let

(r)

→ N

be a colouring. Then there exists

D ⊆

[

] and an infinite subset

X ⊆ N

such

that for all

x, y ∈ X

(r)

, we have

(

) =

(

) if

} ⊇ D

, where

x = {x

< x

< ··· < x

} (and similarly for y).