III Ramsey Theory - Ramsey theory on the integers

2Ramsey theory on the integers

III Ramsey Theory

2 Ramsey theory on the integers

So far, we’ve been talking about what happens when we finitely colour graphs.

What if we k-colour the integers N? What can we say about it?

It is a trivial statement that this colouring has a monochromatic subset, by the

pigeonhole principle. Interesting questions arise when we try to take the additive

structure of

into account. So we could ask, can we find a monochromatic

“copy” of N.

One way to make this question concrete is to ask if there is an infinite

monochromatic arithmetic progression.

The answer is easily a “no”! There are only countably many progressions, so

for each arithmetic progression, we pick two things in the progression and colour

them differently.

We can also construct this more concretely. We can colour the first number

red, the next two blue, the next three red etc. then it is easy to see that it

doesn’t have an infinite arithmetic progression.

···

But this is somewhat silly, because there is clearly a significant amount of

structure in the sequence there. It turns out the following is true:

Theorem

(van der Waerden theorem)

Let

m, k ∈ N

. Then there is some

(

m, k

) such that whenever [

] is

-coloured, then there is a monochromatic

arithmetic progression of length n.

The idea is to do induction on

. We will be using colourings with much

greater than k colours to deduce the existence of W (m, k).

We can try a toy example first. Let’s try to show that

2) exists. Suppose

we have three natural numbers:

By the pigeonhole principle, there must be two things that are the same colour,

say

If this is the case, then if we don’t want to have an arithmetic progression of

length 3, then the fifth number must be blue

We now cut the universe into blocks into 5 things. Again by the pigeonhole

principle, there must be two blocks that look the same. Say it’s this block again.

Now we have two sequences, and the point at the end belongs to both of the

two sequences. And no matter what colour it is, we are done.

For

= 3, we can still find such a block, but now that third point could be a

third colour, say, green. This will not stop us. We can now look at these big

blocks, and we know that eventually, these big blocks must repeat themselves.

Here we did the case

= 2, and we used the pigeonhole principle. When we do

m > 2, we will use van der Waerden theorem for smaller m inductively.

We now come up with names to describe the scenario we had above.

Definition

(Focused progression)

We say a collection of arithmetic progressions

, A

, ··· , A

of length m with

= {a

, a

+ d

, ··· , a

+ (m − 1)d

}

are focused at f if a

+ md

= f for all 1 ≤ i ≤ r.

Example. {1, 4} and {5, 6} are focused at 7.

Definition

(Colour focused progression)

, ··· , A

are focused at

, and

each

is monochromatic and no two are the same colour, then we say they are

colour focused at f.

We can now write the proof.

Proof.

We induct on

. The result is clearly trivial when

= 1, and follows

easily from the pigeonhole principle when m = 2.

Suppose

m >

1, and assume inductively that

(

m −

, k

) exists for any

∈ N.

Here is the claim we are trying to established:

Claim.

For each

r ≤ k

, there is a natural number

such that whenever we

k-colour [n], then either

(i) There exists a monochromatic AP of length m; or

(ii) There are r colour-focused AP’s of length m −1.

It is clear that this claim implies the theorem, as we can pick

. Then if

there isn’t a monochromatic AP of length

, then we look at the colour of the

common focus, and it must be one of the colours of those AP’s.

To prove the claim, we induct on

. When

= 1, we may take

(

m −

, k

Now suppose

r >

1, and some

works for

r −

1. With the benefit of hindsight,

we shall show that

n = W (m −1, k

)2n

works for r.

We consider any

-colouring of [

], and suppose it has no monochromatic

AP of length m. We need to find r colour-focused progressions of length n − 1.

We view this

-colouring of [

] as a

colouring of blocks of length 2

, of

which there are W (m − 1, k

Then by definition of W (m −1, k

), we can find blocks

, B

s+t

, ··· , B

s+(m−2)t

which are coloured identically. By the inductive hypothesis, we know each

contains

r −

1 colour-focused AP’s of length

m −

1, say

, .., A

r−1

with first

terms

, ··· , a

and common difference

, ··· , d

r−1

, and also their focus

because the length of B

is 2n

, not just n

Since we assumed there is no monochromatic progression of length

, we can

assume f has a different colour than the A

Now consider

, A

, ··· , A

r−1

, where

has first term

, common difference

+ 2

, and length

m −

1. This difference sends us to the next block, and then

the next term in the AP. We also pick

to consist of the all the focus of the

blocks B

, namely

= {f, f + 2n

t, ··· , f + 2n

t(m − 2)}

These progressions are monochromatic with distinct colours, and focused at

f + (2n

t)(m − 1). So we are done.

This argument, where one looks at the induced colourings of blocks, is called

a product argument.

The bounds we obtain from this argument are, as one would expect, terrible.

We have

W (3, k) ≤ k

where the tower of k’s has length k −1.

Now we can generalize in a different way. What can we say about monochro-

matic structures a

-colouring of

? What is the right generalization of van

der Waerden theorem?

To figure out the answer, we need to find the right generalization of arithmetic

progressions.

Definition

(Homothetic copy)

Given a finite

S ⊆ N

, a homothetic copy of

is a set of the form

`S + M,

where `, M ∈ N

and ` 6= 0.

Example.

An arithmetic progression of length

is just a homothetic copy of

[m] = {1, 2, ··· , m}.

Thus, the theorem we want to say is the following:

Theorem

(Gallai)

Whenever

-coloured, there exists a monochromatic

(homothetic) copy of S for each finite S ⊆ N

In order to prove this, we prove the beautiful Hales–Jewett theorem, which

is in some sense the abstract core of the argument we used for van der Waerden

theorem.

We need a bit of set up. As usual, we write

[m]

= {(x

, ··· , x

) : x

∈ [m]}.

Here is the important definition:

Definition

(Combinatorial line)

A combinatorial line

L ⊆

[

]

is a set of the

form

{(x

, ··· , x

n) : x

= x

for all i, j ∈ I; x

= a

for all i 6∈ I}

for some fixed non-empty set of coordinates I ⊆ [n] and a

∈ [m].

I is called the set of active coordinates.

Example. Here is a line in [3]

This line is given by I = {1}, a

= 1.

The following shows all the lines we have:

It is easy to see that any line has exactly [

] elements. We write

−

and

for the first and last point of the line, i.e. the points where the active coordinates

are all 1 and

respectively. It is clear that any line

is uniquely determined

by L

−

and its active coordinates.

Example. In [3]

, we have the line

L = {(1, 2, 1), (2, 2, 2), (3, 2, 3)}.

This is a line with

{

}

and

= 2. The first and last points are (1

and (3, 2, 3).

Then we have the following theorem:

Theorem

(Hales–Jewett theorem)

For all

m, k ∈ N

, there exists

(

m, k

)

such that whenever [m]

is k-coloured, there exists a monochromatic line.

Note that this theorem implies van der Waerden’s theorem easily. The idea

is to embed [

]

into

linearly, so that a monochromatic line in [

]

gives an

arithmetic progression of length

. Explicitly, given a

-colouring

N →

[

we define c

: [m]

→ [k] by

, x

, ··· , x

) = c(x

+ x

+ ··· + x

Now a monochromatic line gives us an arithmetic progression of length m. For

example, if the line is

L = {(1, 2, 1), (2, 2, 2), (3, 2, 3)},

then we get the monochromatic progression 4

8 of length 3. In general, the

monochromatic AP defined has d = |I|.

The proof is essentially what we did for van der Waerden theorem. We are

going to build a lot of almost-lines that point at the same vertex, and then no

matter what colour the last vertex is, we are happy.

Definition

(Focused lines)

We say lines

, ··· , L

are focused at

f ∈

[

]

= f for all i = 1, ··· , r.

Definition

(Colour focused lines)

, ··· , L

are focused lines, and

\{L

}

is monochromatic for each

= 1

, ··· , r

and all these colours are distinct, then

we say L

, ··· , L

are colour focused at f.

Proof.

We proceed by induction on

. This is clearly trivial for

= 1, as a line

only has a single point.

Now suppose

m >

1, and that

(

m −

, k

) exists for all

k ∈ N

. As before,

we will prove the following claim:

Claim.

For each 1

≤ r ≤ k

, there is an

n ∈ N

such that in any

-colouring of

[m]

, either

(i) there exists a monochromatic line; or

(ii) there exists r colour-focused lines.

Again, the result is immediate from the claim, as we just use it for

and

look at the colour of the focus.

The prove this claim, we induct on

. If

= 1, then picking

(

m−

, k

)

works, as a single colour-focused line of length

is just a monochromatic line of

length n −1, and [m −1]

⊆ [m]

naturally.

Now suppose

r >

1 and

works for

r −

1. Then we will show that

works, where

= HJ(m − 1, k

Consider a colouring

: [

]

n+n

→

[

], and we assume this has no monochromatic

lines.

We think of [

]

n+n

as [

]

[

]

. So for each point in [

]

, we have

a whole cube [

]

. Consider a

colouring of [

]

as follows — given any

x ∈

[

]

, we look at the subset of [

]

n+n

containing the points with last

coordinates

. Then we define the new colouring of [

]

to be the restriction

of c to this [m]

, and there are m

possibilities.

Now there exists a line

such that

L \ L

is monochromatic for the new

colouring. This means for all a ∈ [m]

and for all b, b

∈ L \ L

, we have

c(a, b) = c(a, b

Let

(

) denote this common colour for all

a ∈

[

]

. this is a

-colouring of

[

]

with no monochromatic line (because

doesn’t have any). So by definition

, there exists lines

, L

, ··· , L

r−1

in [

]

which are colour-focused at some

f ∈ [m]

for c

In the proof of van der Waerden, we had a progression within each block,

and also how we just between blocks. Here we have the same thing. We have

the lines in [m]

, and also the “external” line L.

Consider the line L

, L

, ··· , L

r−1

in [m]

n+n

, where

)

−

= (L

−

, L

−

and the active coordinate set is

∪ I

, where

is the active coordinate set of

Also consider the line F with F

−

= (f, L

−

) and active coordinate set I.

Then we see that

, ··· , L

r−1

, F

are

colour-focused lines with focus

(f, L

We can now prove our generalized van der Waerden.

Theorem

(Gallai)

Whenever

-coloured, there exists a monochromatic

(homothetic) copy of S for each finite S ⊆ N

Proof.

Let

(1)

, S

(2)

, ··· , S

(

)

} ⊆ N

. Given a

-colouring

→

[

], we

induce a k-colouring c : [m]

→ [k] by

, ··· , x

) = c(S(x

) + S(x

) + ··· + S(x

)).

By Hales-Jewett, for sufficiently large

, there exists a monochromatic line

for

, which gives us a monochromatic homothetic copy of

. For example, if

the line is (1 2 1), (2 2 2) and (3 2 3), then we know

c(S(1) + S(2) + S(1)) = c(S(2) + S(2) + S(2)) = c(S(3) + S(2) + S(3)).

So we have the monochromatic homothetic copy

λS

, where

= 2 (the

number of active coordinates), and µ = S(2).

Largeness in Ramsey theory*

In van der Waerden, we proved that for each

k, m

, there is some

such that

whenever we

-colour [

], then there is a monochromatic AP of length

. How

much of this is relies on the underlying set being [

]? Or is it just that if we

finitely colour [

], then one of the colours must contain a lot of numbers, and if

we have a lot of numbers, then we are guaranteed to have a monochromatic AP?

Of course, by “contains a lot of numbers”, we do not mean the actual number

of numbers we have. It is certainly not true that for some

, whenever we

-colour any set of

integers, we must have a monochromatic

-AP, because

an arbitrary set of

integers need not even contain an

-AP at all, let alone a

monochromatic one. Thus, what we really mean is density.

Definition (Density). For A ⊆ N, we let the density of A as

d(A) = lim sup

(b−a)→∞

A ∩ [a, b]

|b − a|

Clearly, in any finite

-colouring of

, there exists a colour class with positive

density. Thus, we want to know if merely a positive density implies the existence

of progressions. Remarkably, the answer is yes!

Theorem

(Szemer´edi theorem)

Let

δ >

0 and

m ∈ N

. Then there exists some

(

m, δ

)

∈ N

such that any subset

A ⊆

[

] with

|A| ≥ δN

contains an

m-term arithmetic progression.

The proof of this theorem is usually the subject of an entire lecture course,

so we are not going to attempt to prove this. Even the particular case

= 3 is

very hard.

This theorem has a lot of very nice Ramsey consequences. In the case of

graph colourings, we asked ourselves what happens if we colour a graph with

infinitely many colours. Suppose we now have a colouring

N → N

. Can we

still find a monochromatic progression of length

? Of course not, because

can be injective.

Theorem. For any c : N → N, there exists a m-AP on which either

(i) c is constant; or

(ii) c is injective.

It is also possible to prove this directly, but it is easy with Szemer´edi.

Proof. We set

δ =

(m + 1)

We let N = S(m, δ). We write

[N] = A

∪ A

∪ ··· ∪ A

where the

’s are the colour-classes of

[N]

. By choice of

, we are done if

| ≥ δN for some 1 ≤ i ≤ k. So suppose not.

Let’s try to count the number of arithmetic progressions in [

]. There are

more than

(

+ 1)

of these, as we can take any

a, d ∈

[

N/m

+ 1]. We want

to show that there is an AP that hits each A

at most once.

So, fixing an

, how many AP’s are there that hit

at least twice? We need

to pick two terms in

, and also decide which two terms in the progression they

are in, e.g. they can be the first and second term, or the 5th and 17th term. So

there are at most m

terms.

So the number of AP’s on which c is injective is greater than

(m + 1)

− k|A

≥

(m + 1)

−

(δN)

(m + 1)

− δN

≥ 0.

So we are done. Here the first inequality follows from the fact that

= [

]

and each |A

| < δN.

Our next theorem will mix arithmetic and graph-theoretic properties. Con-

sider a colouring

(2)

→

[2]. As before, we say a set

is monochromatic if

(2)

is constant. Now we want to try to find a monochromatic set with some

arithmetic properties.

The first obvious question to ask is — can we find a monochromatic 3-term

arithmetic progression? The answer is no. For example, we can define

(

) to be

the parity of largest power of 2 dividing

j −i

, and then there is no monochromatic

3-term arithmetic progression.

What if we make some concessions — can we find a blue 10-AP, or if not,

find an infinite red set? The answer is again no. This construction is slightly

more involved. To construct a counterexample, we can make progressively larger

red cliques, and take all other edges blue. If we double the size of the red cliques

every time, it is not hard to check that there is no blue 4-AP, and no infinite

red set.

···

What if we further relax our condition, and only require an arbitrarily large red

set?

Theorem. For any c : N

(2)

→ {red, blue}, either

(i) There exists a blue m-AP for each m ∈ N; or

(ii) There exists arbitrarily large red sets.

Proof.

Suppose we can’t find a blue

-AP for some fixed

. We induct on

and try to find a red set of size r.

Say

A ⊆ N

is a progression of length

. Since

has no blue

-term

progression, so it must contain many red edges. Indeed, each

-AP in

must

contain a red edge. Also each edge specifies two points, and this can be extended

to an

-term progression in at most

ways. Since there are

(

+ 1)

. So

there are at least

(m + 1)

red edges. With the benefit of hindsight, we set

δ =

(m + 1)

The idea is that since we have lots of red edges, we can try to find a point with

a lot of red edges connected to it, and we hope to find a progression in it.

We say X, Y ⊆ N form an (r, k)-structure if

(i) They are disjoint

(ii) X is red;

(iii) Y is an arithmetic progression;

(iv) All X-Y edges are red;

(v) |X| = r and |Y | = k.

···

We show by induction that there is an (r, k)-structure for each r and k.

A (1

, k

) structure is just a vertex connected by red edges to a

-point structure.

If we take

(

δ, k

), we know among the first

natural numbers, there are

at least

(

+ 1)

) red edges inside [

]. So in particular, some

v ∈

[

]

has at least

δN

red neighbours in [

], and so we know

is connected to some

k-AP by red edges. That’s the base case done.

Now suppose we can find an (r − 1, k

)-structure for all k

∈ N. We set

= S



(m + 1)

, k



We let (

X, Y

) be an (

r −

, k

)-structure. As before, we can find

v ∈ Y

such

that

has

δ|Y |

red neighbours in

. Then we can find a progression

length

in the red neighbourhood of

, and we are done, as (

X ∪ {v}, Y

) is an

(

r, k

)-structure, and an “arithmetic progression” within an arithmetic progression

is still an arithmetic progression.

Before we end this chapter, we make a quick remark. Everything we looked

for in this chapter involved the additive structure of the naturals. What about

the multiplicative structure? For example, given a finite colouring of

, can we

find a monochromatic geometric progression? The answer is trivially yes. We

can look at

{

x ∈ N}

, and then multiplication inside this set just looks like

addition in the naturals.

But what if we want to mix additive and multiplicative structures? For

example, can we always find a monochromatic set of the form

y, xy}

? Of

course, there is the trivial answer

= 2, but is there any other? This

question was answered positively in 2016! We will return to this at the end of

the course.