Part III — Ramsey Theory

Based on lectures by B. P. Narayanan

Notes taken by Dexter Chua

Lent 2017

These notes are not endorsed by the lecturers, and I have modified them (often
significantly) after lectures. They are nowhere near accurate representations of what
was actually lectured, and in particular, all errors are almost surely mine.

What happens when we cut up a mathematical structure into many ‘pieces’ ? How
big must the original structure be in order to guarantee that at least one of the pieces
has a specific property of interest? These are the kinds of questions at the heart of
Ramsey theory. A prototypical result in the area is van der Waerden’s theorem, which
states that whenever we partition the natural numbers into finitely many classes, there
is a class that contains arbitrarily long arithmetic progressions.

The course will cover both classical material and more recent developments in the
subject. Some of the classical results that I shall cover include Ramsey’s theorem, van
der Waerden’s theorem and the Hales–Jewett theorem; I shall discuss some applications
of these results as well. More recent developments that I hope to cover include the
properties of non-Ramsey graphs, topics in geometric Ramsey theory, and finally,
connections between Ramsey theory and topological dynamics. I will also indicate a
number of open problems.

Pre-requisites

There are almost no pre-requisites and the material presented in this course will, by
and large, be self-contained. However, students familiar with the basic notions of graph
theory and point-set topology are bound to find the course easier.

1
Contents III Ramsey Theory

Contents
0 Introduction 3

1 Graph Ramsey theory 5

1.1 Infinite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Finite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Ramsey theory on the integers 18

3 Partition Regularity 27

4 Topological Dynamics in Ramsey Theory 38

5 Sums and products* 49

Index 52

2
0 Introduction III Ramsey Theory

0 Introduction
Vaguely, the main idea of Ramsey theory is as follows — we have some object
X that comes with some structure, and then we break X up into finitely many
pieces. Can we find a piece that retains some of the structure of X? Usually, we
phrase this in terms of colourings. We pick a list of finitely many colours, and
colour each element of X. Then we want to find a monochromatic subset of X
that satisfies some properties.
The most classical example of this is a graph colouring problem. We take a
graph, say

We then colour each edge with either red or blue:

We now try to find a (complete) subgraph that is monochromatic, i.e. a subgraph

all of whose edges are the same colour. With a bit of effort, we can find a red
monochromatic subgraph of size 4:

Are we always guaranteed that we can find a monochromatic subgraph of size 4?

If not, how big does the initial graph have to be? These are questions we will
answer in this course. Often, we will ask the question in an “infinite” form —
given an infinite graph, is it always possible to find an infinite monochromatic
subgraph? The answer is yes, and it turns out we can deduce results about the
finitary version just by knowing the infinite version.
These questions about graphs will take up the first chapter of the course.
In the remaining of the course, we will discuss Ramsey theory on the integers,
which, for the purpose of this course, will always mean N = {1, 2, 3, · · · }. We will
now try to answer questions about the arithmetic structure of N. For example,
when we finitely colour N, can we find an infinite arithmetic progression? With
some thought, we can see that the answer is no. However, it turns out we can
find arbitrarily long arithmetic progressions.

3
0 Introduction III Ramsey Theory

More generally, suppose we have some system of linear equations

3x + 6y + 2z = 0
2x + 7y + 3z = 0.

If we finitely colour N, can we always find a monochromatic solution to these

equations?
Remarkably, there is a complete characterization of all linear systems that
always admit monochromatic solutions. This is given by Rado’s theorem, which
is one of the hardest theorems we are going to prove in the course.
If we are brave, then we can try to get the multiplicative structure of N in
the picture. We begin by asking the most naive question — if we finitely colour
N, can we always find x, y ∈ N, not both 2, such that x + y and xy are the same
colour? This is a very hard question, and the answer turns out to be yes.

4
1 Graph Ramsey theory III Ramsey Theory

1 Graph 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 i1 i2 · · · ir for an r-set, and implicitly assume i1 < i2 < · · · < ir .
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

(
red i + j is even
c(ij) = .
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 : 2n | i + j} mod 3

In this case, taking X = {8, 82 , 83 , · · · } gives an infinite monochromatic set of

colour 0.

5
1 Graph Ramsey theory III Ramsey Theory

Example. Let c : N(2) → {red, blue} by

(
red i + j has an even number of distinct prime factors
c(ij) =
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 a1 ∈ N. Then by the pigeonhole principle, there

must exist an infinite set B1 ⊆ N \ {a1 } such that all the a1 -B1 edges (i.e. edges
of the form (a1 , b1 ) with b1 ∈ B1 ) are of the same colour c1 .
Now again arbitrarily pick an element a2 ∈ B1 . Again, we find some infinite
B2 ⊆ B1 such that all a2 -B2 edges are the same colour c2 . We proceed inductively.

a2

a1

We obtain a sequence {a1 , a2 , · · · } and a sequence of colours {c1 , c2 , · · · } such

that c(ai , aj ) = ci , for i < j.
Now again by the pigeonhole principle, since there are finitely many colours,
there exists an infinite subsequence ci1 , ci2 , · · · that is constant. Then ai1 , ai2 , · · ·
is an infinite monochromatic set, since all edges are of the colour ci1 = ci2 = · · · .
So we are done.
This proof exhibits many common themes we will see in the different Ramsey
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.

6
1 Graph Ramsey theory III Ramsey Theory

Corollary (Bolzano-Weierstrass theorem). Let (xi )i≥0 be a bounded sequence

of real numbers. Then it has a convergent subsequence.

Proof. We define a colouring c : N(2) → {↑, ↓}, where

(
↑ xi < xj
c(ij) =
↓ xj ≤ xi

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

(
red i | j + k
c(ijk) =
blue otherwise

Then X = {20 , 21 , 22 , · · · } is an infinite monochromatic set.

Proof. We induct on r. This is trivial when r = 1. Assume r > 1. We fix a1 ∈ N.
We induce a k-colouring c1 of (N \ {a1 })(r−1) by

c1 (F ) = c(F ∪ {a1 }).

By induction, there exists an infinite B1 ⊆ N\{a1 } such that B1 is monochromatic

for c1 , i.e. all a1 -B1 r-sets have the same colour c1 .
We proceed inductively as before. We get a1 , a2 , a3 , · · · and colours c1 , c2 , · · ·
etc. such that for any r-set F contained in {a1 , a2 , · · · }, we have c(F ) = cmin F .
Then again, there exists ci1 , ci2 , ci3 , · · · all identical, and our monochromatic
set is {ai1 , ai2 , ai3 , · · · }.
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:

...

7
1 Graph Ramsey theory III Ramsey Theory

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 c1 be a 2-colouring

(
SAME c(ij) = c(k`)
c1 (ijk`) =
DIFF otherwise

Then we know there is some infinite monochromatic set X1 ⊆ N for c1 . If X1 is

coloured SAME, then we are done. Indeed, for any pair ij and i0 j 0 in X1 , we can
pick some huge k, ` such that j, j 0 < k < `, and then

c(ij) = c(k`) = c(i0 j 0 )

as we know c1 (ijk`) = c1 (i0 j 0 k`) = SAME.

What if X1 is coloured DIFF? We next look at what happens when we have
(4)
edges that are nested each other. We define c2 : X1 → {SAME, DIFF} defined by
(
SAME c(i`) = c(jk)
c2 (ijk`) =
DIFF otherwise

Again, we can find an infinite monochromatic subset X2 ⊆ X1 with respect to

c2 .
We now note that X2 cannot be coloured SAME. Indeed, we can just look at

8
1 Graph Ramsey theory III Ramsey Theory

i j k ` m n

So if X2 were SAME, we would have

c(`m) = c(in) = c(jk),
which is impossible since X1 is coloured DIFF under c1 .
(4)
So X2 is DIFF. Now consider c3 : X2 → {SAME, DIFF} given by
(
SAME c(ik) = c(j`)
c3 (ijk`) =
DIFF otherwise

Again find an infinite monochromatic subset X3 ⊆ X2 for c3 . Then X3 cannot

be SAME, this time using the following picture:

contradicting the fact that c2 is DIFF. So we know X3 is DIFF.

We have now have ended up in this set X3 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 c4 :
(3)
X3 → {SAME, DIFF} given by
(
SAME c(ij) = c(jk)
c4 (ijk) =
DIFF otherwise

Let X4 ⊆ X3 be an infinite monochromatic set for c4 . Now X4 cannot be

coloured SAME, using the following picture:

which contradicts the fact that c1 is DIFF. So we know X4 is also coloured DIFF
under c4 .
We are almost there. We need to deal with edges that nest in the sense of
(3)
(iii) and (iv). We look at c5 : X4 → {LSAME, LDIFF} given by
(
LSAME c(ij) = c(ik)
c5 (ijk) =
LDIFF otherwise

9
1 Graph Ramsey theory III Ramsey Theory

Again we find X5 ⊆ X4 , an infinite monochromatic set for c5 . We don’t separate

into cases yet, because we know both cases are possible, but move on to classify
(3)
the right case as well. Define c6 : X5 → {RSAME, RDIFF} given by
(
RSAME c(ik) = c(jk)
c5 (ijk) =
RDIFF otherwise

Let X6 ⊆ X5 be an infinite monochromatic subset under c5 .

As before, we can check that it is impossible to get both LSAME and RSAME,
using the following picture:

contradicting c4 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 (c1 , c2 , c3 , c4 , c5 , c6 ) 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 2r 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 : xi = yi } ⊇ D, where
x = {x1 < x2 < · · · < xr } (and similarly for y).

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 Pn is

10
1 Graph Ramsey theory III Ramsey Theory

We can write
V = [n], E = {12, 23, 34, · · · , (n − 1)n}.

Example. The n-cycle Cn is

V = [n], E = {12, 23, · · · , (n − 1)n, 1n}.

Finally, we have

Example. The complete graph Vn 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(Kn ) to be the smallest N ∈ N
whenever we red-blue colour the edges of KN , then there is a monochromatic
copy of Kn .
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 cm of Km = [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 M1 ⊆ N and some
fixed 2-colouring dn of [n] such that cm |[n](2) = dn for all m ∈ M1 .

11
1 Graph Ramsey theory III Ramsey Theory

Similarly, there exists an infinite M2 ⊆ M1 such that cm |[n+1](2) = dn+1 for

m ∈ M2 , again for some 2-colouring dn+1 of [n + 1]. We repeat this over and
over again. Then we get a sequence dn , dn+1 , · · · of colourings such that di is a
2-colouring of [i](2) without a monochromatic Kn , and further for i < j, we have
dj |[i](2) = di .
We then define a 2-colouring c of N(2) by
c(ij) = dm (ij)
for any m > i, j. Clearly, there exists no monochromatic Kn in c, as any Kn 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 pij for
each ij ∈ N(2) . We will think of the edge ij as red if pij = >, and blue if pij = ⊥.
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 pij 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
1
d(f, g) = n if n = min{i : fi 6= gi }.
2
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 a1 . Then
there are some things that are connected by red to it, and others connected by
blue:

a1

12
1 Graph Ramsey theory III Ramsey Theory

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
Kn in the red set, then we are done. But on the other hand, we only need a red
Kn−1 , and not a full blown Kn . 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(Kn , Km )
to be the minimum N ∈ N such that whenever we red-blue colour the edges of
KN , we either get a red Kn or a blue Km .
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

 
n+m−1
R(n, m) ≤ .
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 KN and any vertex v ∈ V (Kn ). We write

v(Kn ) \ {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 Km or a red copy of Kn−1 . In the first case, we are done, and in the
second case, we just add v to the red Kn−1 .
The last formula is just a straightforward property of binomial coefficients.
In particular, we find
4n
 
2n − 1
R(n) ≤ ≤√ .
n−2 n
We genuinely have no idea whether ∼ 4n 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
4n
R(n) ≤ c .
n

13
1 Graph Ramsey theory III Ramsey Theory

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ös.
√ n
Theorem. We have R(n) ≥ 2 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.
√ n
Proof. Let N ≤ 2 . We perform a red-blue colouring of KN randomly, where
each edge is coloured red independently of the others with probability 12 .
We let XR be the number of red copies of Kn in such a colouring. Then
since expectation is linear, we know the expected value is
   (n2 )
N 1
[XR ] =
n 2
 n  (n2 )
eN 1
≤
n 2
 e n √ n2 √ −n2
≤ 2 2
ne n

=
n
1
<
2
for sufficiently large n.
Similarly, we have [XB ] < 12 . So the expected number of monochromatic Kn
is < 1. So in particular there must be some colouring with no monochromatic
Kn .
Recall the bound  
m+n−2
R(m, n) ≤ .
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
 
n+1 n(n + 1)
R(3, n) ≤ = ∼ n2 .
2 2
We can sort-of imagine where this bound came from. Suppose we randomly pick
a vertex v1 . 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 Kn .
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 v2 connected to v1 by a blue edge, and do the
same thing to v2 . We keep going on, and by the time we reach vn , we would
have found v1 , · · · , vn all connected to each other by blue edges, and we are
done. So we have K(3, n) ∼ n2 .

14
1 Graph Ramsey theory III Ramsey Theory

v1 v2 v3

But this argument is rather weak, because we didn’t use that large pool of blue
edges we’ve found at v1 . So in fact this time we can do better than n2 .
Theorem. We have
100n2
R(3, n) ≤
log n
for sufficiently large n ∈ N.

Here the 100 is, obviously, just some random big number.
Proof. Let N ≥ 100n2 / log n, and consider a red-blue colouring of the edges of
KN with no red K3 . We want to find a blue Kn 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 v1 , v2 , v3 such that v1 v2 and v1 v3 are red, then v2 v3 is blue:

v2

v1 v3

We now let

F = {W : W ⊆ V (KN ) such that W (2) is monochromatic and blue}.

We want to find some W ∈ F such that |W | ≥ n, i.e. a blue Kn . 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 (KN ), we define the variable

Xv = n1{v∈W } + |{u : uv is red and u ∈ W }|.

Claim.
log n
E[Xv ] >
10
for each vertex v.
To see this, let
A = {u : uv is red}
and let
B = {u : uv is blue}.

15
1 Graph Ramsey theory III Ramsey Theory

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
T

a1

S
B

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 2x + 1 choices of W . So we know
n 2x
E[Xv | W ∩ B = S] ≥ + (E[|random subset of T|])
2x + 1 2x + 1
n 2x−1 x
= x + x .
2 +1 2 +1
Now if
log n
x< ,
2
then
n n log n
≥√ ≥
2x + 1 n+1 10
for all sufficiently large n. On the other hand, if
log n
x≥ ,
2
then
2x−1 x 1 log n log n
x
≥ · ≥ .
2 +1 4 2 10
So we are done.
Claim. X
Xv ≤ 2n|W |.
v∈V

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”).

16
1 Graph Ramsey theory III Ramsey Theory

Finally, we know that

1 X N log n 100n2 log n

E[|W |] ≥ E[XV ] ≥ ≥ · ≥ 5n.
2n 2n 10 log n 20n

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 KN 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(Pn , Pn ) ≤ 2n.
So sometimes it can be much better.

17
2 Ramsey 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 N 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 N =
W (m, k) such that whenever [N ] is k-coloured, then there is a monochromatic
arithmetic progression of length n.
The idea is to do induction on m. 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 W (3, 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.

18
2 Ramsey theory on the integers III Ramsey Theory

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 k = 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 m = 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
A1 , A2 , · · · , Ar of length m with

Ai = {ai , ai + di , · · · , ai + (m − 1)di }

are focused at f if ai + mdi = f for all 1 ≤ i ≤ r.

Example. {1, 4} and {5, 6} are focused at 7.
Definition (Colour focused progression). If A1 , · · · , Ar are focused at f , and
each Ai 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 m. The result is clearly trivial when m = 1, and follows
easily from the pigeonhole principle when m = 2.
Suppose m > 1, and assume inductively that W (m − 1, k 0 ) exists for any
0
k ∈ N.
Here is the claim we are trying to established:
Claim. For each r ≤ k, there is a natural number n 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 r = k. Then if
there isn’t a monochromatic AP of length m, 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 r. When n = 1, we may take W (m − 1, k).
Now suppose r > 1, and some n0 works for r − 1. With the benefit of hindsight,
we shall show that 0
n = W (m − 1, k 2n )2n0
works for r.
We consider any k-colouring of [n], and suppose it has no monochromatic
AP of length m. We need to find r colour-focused progressions of length n − 1.

19
2 Ramsey theory on the integers III Ramsey Theory

0
We view this k-colouring of [n] as a k 2n colouring of blocks of length 2n0 , of
0
which there are W (m − 1, k 2n ).
0
Then by definition of W (m − 1, k 2n ), we can find blocks
Bs , Bs+t , · · · , Bs+(m−2)t
which are coloured identically. By the inductive hypothesis, we know each Bs
contains r − 1 colour-focused AP’s of length m − 1, say A1 , .., Ar−1 with first
terms a1 , · · · , ar and common difference d1 , · · · , dr−1 , and also their focus f ,
because the length of Bs is 2n0 , not just n0 .
Since we assumed there is no monochromatic progression of length n, we can
assume f has a different colour than the Ai .
Now consider A01 , A02 , · · · , A0r−1 , where A0i has first term ai , common difference
di + 2n0 t, and length m − 1. This difference sends us to the next block, and then
the next term in the AP. We also pick A0r to consist of the all the focus of the
blocks Bi , namely
A0r = {f, f + 2n0 t, · · · , f + 2n0 t(m − 2)}
These progressions are monochromatic with distinct colours, and focused at
f + (2n0 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 4k k
..
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 k-colouring of Nd ? 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 ⊆ Nd , a homothetic copy of S
is a set of the form
`S + M,
where `, M ∈ Nd and ` 6= 0.
Example. An arithmetic progression of length m is just a homothetic copy of
[m] = {1, 2, · · · , m}.
Thus, the theorem we want to say is the following:
Theorem (Gallai). Whenever Nd is k-coloured, there exists a monochromatic
(homothetic) copy of S for each finite S ⊆ Nd .
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]n = {(x1 , · · · , xn ) : xi ∈ [m]}.
Here is the important definition:

20
2 Ramsey theory on the integers III Ramsey Theory

Definition (Combinatorial line). A combinatorial line L ⊆ [m]n is a set of the

form
{(x1 , · · · , xn n) : xi = xj for all i, j ∈ I; xi = ai for all i 6∈ I}
for some fixed non-empty set of coordinates I ⊆ [n] and ai ∈ [m].
I is called the set of active coordinates.
Example. Here is a line in [3]2

This line is given by I = {1}, a2 = 1.

The following shows all the lines we have:

It is easy to see that any line has exactly [m] elements. We write L− and L+
for the first and last point of the line, i.e. the points where the active coordinates
are all 1 and m respectively. It is clear that any line L is uniquely determined
by L− and its active coordinates.
Example. In [3]3 , we have the line
L = {(1, 2, 1), (2, 2, 2), (3, 2, 3)}.
This is a line with I = {1, 3} and a2 = 2. The first and last points are (1, 2, 1)
and (3, 2, 3).
Then we have the following theorem:
Theorem (Hales–Jewett theorem). For all m, k ∈ N, there exists N = HJ(m, k)
such that whenever [m]N is k-coloured, there exists a monochromatic line.
Note that this theorem implies van der Waerden’s theorem easily. The idea
is to embed [m]N into N linearly, so that a monochromatic line in [m]N gives an
arithmetic progression of length m. Explicitly, given a k-colouring c : N → [k],
we define c0 : [m]N → [k] by
c0 (x1 , x2 , · · · , xN ) = c(x1 + x2 + · · · + xN ).
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, 6, 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.

21
2 Ramsey theory on the integers III Ramsey Theory

Definition (Focused lines). We say lines L1 , · · · , Lr are focused at f ∈ [m]N if

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

Definition (Colour focused lines). If L1 , · · · , Lr are focused lines, and Li \{L+

i }
is monochromatic for each i = 1, · · · , r and all these colours are distinct, then
we say L1 , · · · , Lr are colour focused at f .
Proof. We proceed by induction on m. This is clearly trivial for m = 1, as a line
only has a single point.
Now suppose m > 1, and that HJ(m − 1, 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 k-colouring of
[m]n , 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 r = k and
look at the colour of the focus.
The prove this claim, we induct on r. If r = 1, then picking n = HJ(m − 1, k)
works, as a single colour-focused line of length n is just a monochromatic line of
length n − 1, and [m − 1]n ⊆ [m]n naturally.
Now suppose r > 1 and n works for r − 1. Then we will show that n + n0
works, where n
n0 = HJ(m − 1, k m ).
0
Consider a colouring c : [m]n+n → [k], and we assume this has no monochromatic
lines.
0 0 0
We think of [m]n+n as [m]n × [m]n . So for each point in [m]n , we have
n mn n0
a whole cube [m] . Consider a k colouring of [m] as follows — given any
0 0
x ∈ [m]n , we look at the subset of [m]n+n containing the points with last n0
0
coordinates x. Then we define the new colouring of [m]n to be the restriction of
n n
c to this [m] , and there are m possibilities.
Now there exists a line L such that L \ L+ is monochromatic for the new
colouring. This means for all a ∈ [m]n and for all b, b0 ∈ L \ L+ , we have
c(a, b) = c(a, b0 ).
Let c00 (a) denote this common colour for all a ∈ [m]n . this is a k-colouring of
[m]n with no monochromatic line (because c doesn’t have any). So by definition
of n, there exists lines L1 , L2 , · · · , Lr−1 in [m]n which are colour-focused at some
f ∈ [m]n for c00 .
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]n , and also the “external” line L.

22
2 Ramsey theory on the integers III Ramsey Theory

0
Consider the line L01 , L02 , · · · , L0r−1 in [m]n+n , where

(L0i )− = (L− −
i , L ),

and the active coordinate set is Ii ∪ I, where I is the active coordinate set of L.
Also consider the line F with F − = (f, L− ) and active coordinate set I.
Then we see that L01 , · · · , L0r−1 , F are r colour-focused lines with focus
(f, L+ ).

We can now prove our generalized van der Waerden.

Theorem (Gallai). Whenever Nd is k-coloured, there exists a monochromatic
(homothetic) copy of S for each finite S ⊆ Nd .
Proof. Let S = {S(1), S(2), · · · , S(m)} ⊆ Nd . Given a k-colouring Nd → [k], we
induce a k-colouring c : [m]N → [k] by

c0 (x1 , · · · , xN ) = c(S(x1 ) + S(x2 ) + · · · + S(xN )).

By Hales-Jewett, for sufficiently large N , there exists a monochromatic line L for

c0 , which gives us a monochromatic homothetic copy of S in Nd . 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 n such that
whenever we k-colour [n], then there is a monochromatic AP of length m. How
much of this is relies on the underlying set being [n]? Or is it just that if we
finitely colour [n], 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 n, whenever we
k-colour any set of n integers, we must have a monochromatic m-AP, because
an arbitrary set of n integers need not even contain an m-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

¯ A ∩ [a, b]
d(A) = lim sup .
(b−a)→∞ |b − a|

Clearly, in any finite k-colouring of N, 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édi theorem). Let δ > 0 and m ∈ N. Then there exists some
N = S(m, δ) ∈ N such that any subset A ⊆ [N ] with |A| ≥ δN contains an
m-term arithmetic progression.

23
2 Ramsey theory on the integers III Ramsey Theory

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 m = 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 c : N → N. Can we
still find a monochromatic progression of length m? Of course not, because c
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édi.

Proof. We set
1
δ= .
m2 (m + 1)2
We let N = S(m, δ). We write

[N ] = A1 ∪ A2 ∪ · · · ∪ Ak ,

where the Ai ’s are the colour-classes of c|[N ] . By choice of N , we are done if

|Ai | ≥ δN for some 1 ≤ i ≤ k. So suppose not.
Let’s try to count the number of arithmetic progressions in [N ]. There are
more than N 2 /(m + 1)2 of these, as we can take any a, d ∈ [N/m + 1]. We want
to show that there is an AP that hits each Ai at most once.
So, fixing an i, how many AP’s are there that hit Ai at least twice? We need
to pick two terms in Ai , 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 m2 |Ai |2 terms.
So the number of AP’s on which c is injective is greater than

N2 2 2 N2 1 2 2 N2
− k|A i | m ≥ − (δN ) m = − δN 2 m2 ≥ 0.
(m + 1)2 (m + 1)2 δ (m + 1)2
P
So we are done. Here the first inequality follows from the fact that |Ai | = [N ]
and each |Ai | < δN .
Our next theorem will mix arithmetic and graph-theoretic properties. Con-
sider a colouring c : N(2) → [2]. As before, we say a set X is monochromatic if
c|X (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 c(ij) 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

24
2 Ramsey theory on the integers III Ramsey Theory

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 m-AP for some fixed m. We induct on r,
and try to find a red set of size r.
Say A ⊆ N is a progression of length N . Since A has no blue m-term
progression, so it must contain many red edges. Indeed, each m-AP in A must
contain a red edge. Also each edge specifies two points, and this can be extended
to an m-term progression in at most m2 ways. Since there are N 2 /(m + 1)2 . So
there are at least
N2
m2 (m + 1)2
red edges. With the benefit of hindsight, we set
1
δ= .
2m2 (m + 1)2

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.

···

25
2 Ramsey theory on the integers III Ramsey Theory

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 k-point structure.
If we take N = S(δ, k), we know among the first N natural numbers, there are
at least N 2 /(m2 (m + 1)2 ) red edges inside [N ]. So in particular, some v ∈ [N ]
has at least δN red neighbours in [N ], and so we know v is connected to some
k-AP by red edges. That’s the base case done.
Now suppose we can find an (r − 1, k 0 )-structure for all k 0 ∈ N. We set
 
1
k0 = S , k .
2m2 (m + 1)2

We let (X, Y ) be an (r − 1, k 0 )-structure. As before, we can find v ∈ Y such

that v has δ|Y | red neighbours in Y . Then we can find a progression Y 0 of
length k in the red neighbourhood of v, and we are done, as (X ∪ {v}, Y 0 ) 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 N, can we
find a monochromatic geometric progression? The answer is trivially yes. We
can look at {2x : 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 {x + y, xy}? Of
course, there is the trivial answer x = y = 2, but is there any other? This
question was answered positively in 2016! We will return to this at the end of
the course.

26
3 Partition Regularity III Ramsey Theory

3 Partition Regularity
In the previous chapter, the problems we studied were mostly “linear” in nature.
We had some linear system, namely that encoding the fact that a sequence is an
AP, and we wanted to know if it had a monochromatic solution. More generally,
we can define the following:
Definition (Partition regularity). We say an m × n matrix A over Q is partition
regular if whenever N is finitely coloured, there exists an x ∈ Nn such that
Ax = 0 and x is monochromatic, i.e. all coordinates of x have the same colour.
Recall that N does not include 0.
There is no loss in generality by assuming A in fact has entries in Z, by
scaling A, but sometimes it is (notationally) convenient to consider cases where
the entries are rational.
The question of the chapter is the following — when is a matrix partition
regular? We begin by looking at some examples.

Example (Schur’s theorem). Schur’s theorem says whenever N is finitely

coloured, there exists a monochromatic

set of the form {x, y, x + y}. In other
words the matrix 1 1 −1 is partition regular, since
 

x
1 1 −1 y  = 0 ⇐⇒ z = x + y.
z


Example. How about 2 3 −5 . This is partition regular, because we can
pick any x, and we have
 

x
2 3 −5 x = 0.
x

This is a trivial example.

How about van der Waerden’s theorem?

Example. Van der Waerden’s theorem says there is a monochromatic 3-AP
{x1 , x2 , x3 } whenever N is finitely-coloured. We know x1 , x2 , x3 forms a 3-AP iff

x3 − x2 = x2 − x1 ,

or equivalently
x3 + x1 = 2x2 .


This implies that 1 −2 1 is partition regular. But this is actually not a
very interesting thing to say, because x1 = x2 = x3 is always a solution to this
equation. So this falls into the previous “trivial” case.
On the second example sheet we saw a stronger version of van der Waerden.
It says we can always find a monochromatic set of the form

{d, a, a + d, a + 2d, · · · , a + md}.

27
3 Partition Regularity III Ramsey Theory

By including this variable, we can write down the property of being a progression
in a non-trivial format by
 
  d
1 1 0 −1  a=0

2 1 −1 0  x2 
x3

This obviously generalizes to an arbitrary m-AP, with matrix

 
1 1 −1 0 0 ··· 0
1
 2 0 −1 0 · · · 0  
1
 3 0 0 −1 · · · 0  .
 .. .. .. .. .. .. .. 
. . . . . . . 
1 m 0 0 0 · · · −1

We’ve seen three examples of partition regular

matrices. Of course, not every
matrix is partition regular. The matrix 1 1 is not partition regular, for the
silly reason that two positive things cannot add up to zero.
Let’s now look at some non-trivial first matrix that is not partition regular.


Example. The matrix 2 −1 is not partition regular, since we can put
c(x) = (−1)n , where n is the maximum integer such that 2n | x. Then {x, 2x} is
never monochromatic.

A similar argument shows that if λ ∈ Q is such that λ, −1 is partition
regular, then λ = 1.


But if we write down a random matrix, say 2 3 −6 ? The goal of this
chapter is to find a complete characterization of matrices that are partition
regular.
Definition (Columns property). Let
 
↑ ↑ ↑
A = c(1) c(2) ··· c(n)  .
↓ ↓ ↓

We say A has the columns property if there is a partition [n] = B1 ∪ B2 ∪ · · · ∪ Bd

such that X
c(i) ∈ span{c(i) : c(i) ∈ B1 ∪ · · · ∪ Bs−1 }
i∈Bs

for s = 1, · · · , d. In particular,
X
c(i) = 0
i∈B1

What does this mean? Let’s look at the matrices we’ve seen so far.


Example. 1 1 −1 has the columns property by picking B1 = {1, 3} and
B2 = {2}.


Example. 2 3 −5 has the columns property by picking B1 = {1, 2, 3}.

28
3 Partition Regularity III Ramsey Theory

Example. The matrix

 
1 1 −1 0 0 ··· 0
1
 2 0 −1 0 ··· 0 

1
 3 0 0 −1 ··· 0 

 .. .. .. .. .. .. .. 
. . . . . . . 
1 m 0 0 0 ··· −1

has the column property. Indeed, we take B1 = {1, 3, · · · , m + 2}, and since
{c(3) , · · · , c(m+2) } spans all of Rm , we know picking B2 = {2} works.



Example. ` −1 has the columns property iff ` = 1. In particular, 1 1
does not have a columns property.
Given these examples, it is natural to conjecture the following:

Theorem (Rado’s theorem). A matrix A is partition regular iff it has the

column property.
This is a remarkable theorem! The property of being partition regular
involves a lot of quantifiers, over infinitely many things, but the column property
is entirely finite, and we can get a computer to check it for us easily.
Another remarkable property of this theorem is that neither direction is obvi-
ous! It turns out partition regularity implies the column property is (marginally)
easier, because if we know something is partition regular, then we can try to
cook up some interesting colourings and see what happens. The other direction
is harder.
To get a feel of the result, we will first prove it in the case of a single equation.
The columns property in particular becomes much simpler. It just means that
there exists a non-empty subset of the non-zero ai ’s that sums up to zero.


Theorem. If a1 , · · · , an ∈ Q \ {0}, then a1 · · · an is partition regular iff
there exists a non-empty I ⊆ [n] such that
X
ai = 0.
i∈I

For a fixed prime p, we let d(x) denote the last non-zero digit of x in base p,
i.e. if
x = dn pn + dn−1 pn−1 + · · · + d0 ,
then
L(x) = min{i : di 6= 0}
and d(x) = dL(x) . We now prove the easy direction of the theorem.


Proposition. If a2 , · · · , an ∈ Q\{0} and a1 a2 · · · an is partition regular,
then X
ai = 0
i∈I

for some non-empty I.

29
3 Partition Regularity III Ramsey Theory

Proof. We wlog ai ∈ Z, by scaling. Fix a suitably large prime

n
X
p> |ai |,
i=1

and consider the (p − 1)-colouring of N where x is coloured d(x). We find

x1 , · · · , xn such that X
ai xi = 0.
and d(xi ) = d for some d ∈ {1, · · · , p − 1}. We write out everything in base p,
and let
L = min{L(xi ) : 1 ≤ i ≤ n},
and set
I = {i : L(xi ) = L}.
Then for all i ∈ I, we have

xi ≡ d (mod pL+1 ).

On the other hand, we are given that

X
ai xi = 0.

Taking mod pL+1 gives us

X
ai d = 0 (mod pL+1 ).
i∈I

Since d is invertible, we know

X
ai = 0 (mod pL+1 ).
i∈I
P
But by our choice of p, this implies that i∈I ai = 0.
Here we knew what prime p to pick ahead. If we didn’t, then we could
consider all primes p, and for each p we find Ip ⊆ [n] such that
X
ai = 0 (mod p).
i∈Ip

Then some Ip has to occur infinitely often, and then we are done. Note that this
is merely about the fact that if a fixed number is 0 mod n for arbitrarily large n,
then it must be zero. This is not some deep local-global correspondence number
theoretic fact.
It turns out this is essentially the only way we know for proving this theorem.
One possible variation is to use the “first non-zero digit” to do the colouring,
but this is harder.
Let’s now try and do the other direction. Before we do that,
we start by
doing a warm up. Last time, we proved that if we had 1 λ , then this is
partition regular iff λ = −1. We now prove a three element version.


Proposition. The equation 1 λ −1 is partition regular for all λ ∈ Q.

30
3 Partition Regularity III Ramsey Theory

Proof. We may wlog λ > 0. If λ = 0, then this is trivial, and if λ < 0, then we
can multiply the whole equation by −1.
Say
r
λ= .
s
The idea is to try to find solutions of this in long arithmetic progressions.
Suppose N is k-coloured. We let

{a, a + d, · · · , a + nd}

be a monochromatic AP, for n sufficiently large.

If sd were the same colour as this AP, then we’d be done, as we can take
r
x = a, y = sd, z = a + sd.
s
n
In fact, if any of sd, 2sd, · · · , r sd have the same colour as the AP, then we’d
be done by taking
r
x = a, y = isd, z = a + isd = a + ird ≤ a + nd.
s
If this were not the case, then {sd, 2sd, · · · , nr sd} is (k − 1)-coloured, and this
 

is just a scaled up copy of N. So we are done by induction on k.

Note that when λ = 1, we have 1 1 −1 is partition regular, and this
may be proved by Ramsey’s theorem. Can we prove this more general result by
Ramsey’s theorem as well? The answer is, we don’t know.
It turns out this is not just a warm up, but the main ingredient of what we
are going to do.


Theorem. If a1 , · · · , an ∈ Q, then a1 · · · an is partition regular iff there
exists a non-empty I ⊆ [n] such that
X
ai = 0.
i∈I

Proof. One direction was done. To do the other direction, we recall that we had
a really easy case of, say,

2 3 −5 ,
because we can just make all the variables the same?
In the general case, we can’t quite do this, but we may try to solve this
equation with the least number of variables possible. In fact, we shall find some
monochromatic x, y, z, and then assign each of x1 , · · · , xn to be one of x, y, z.
We know X
ai = 0.
i∈I

We now partition I into two pieces. We fix i0 ∈ I, and set


x i = i0

xi = y i ∈ I \ {i0 } .

z i 6∈ I


31
3 Partition Regularity III Ramsey Theory

We would be done if whenever we finitely colour N, we can find monochromatic

x, y, z such that
   
X X
ai0 x +  ai  z +  ai  y = 0.
i∈I\{i0 } i6∈I

But, since X
ai = 0,
i∈I

this is equivalent to

ai0 x − ai0 z + (something)y = 0.

Since all these coefficients were non-zero, we can divide out by ai0 , and we are
done by the previous case.
Note that our proof of the theorem shows that if an equation is partition
regular for all last-digit base p colourings, then it is partition regular for all
colourings. This might sound like an easier thing to prove that the full-blown
Rado’s theorem, but it turns out the only proof we have for this implication is
Rado’s theorem.
We now prove the general case. We first do the easy direction, because it is
largely the same as the single-equation case.
Proposition. If A is an m × n matrix with rational entries which is partition
regular, then A has the columns property.

Proof. We again wlog all entries of A are integers. Let the columns of A be
c(1) , · · · , c(n) . Given a prime p, we consider the (p − 1)-colouring of N, where
x is coloured d(x), the last non-zero digit in the base p expansion. Since A is
partition regular, we obtain a monochromatic solution.
We then get a monochromatic x1 , · · · , xn such that Ax = 0, i.e.
X
xi c(i) = 0.

Any such solution with colour d induces a partition of [n] = B1 ∪ B2 ∪ · · · ∪ Br ,

where
– For all i, j ∈ Bs , we have L(xi ) = L(xj ); and
– For all s < t and i ∈ Bs , j ∈ Bt , the L(xi ) < L(xj ).

Last time, with the benefit of hindsight, we were able to choose some large prime
p that made the argument work. So we use the trick we mentioned after the
proof last time.
Since there are finitely many possible partitions of [n], we may assume that
this particular partition is generated by infinitely many primes p. Call these
primes P. We introduce some notation. We say two vectors u, v ∈ Zm satisfy
u ≡ v (mod p) if ui ≡ vi (mod p) for all i = 1, · · · , m.
Now we know that X
xi c(i) = 0.

32
3 Partition Regularity III Ramsey Theory

Looking at the first non-zero digit in the base p expansion, we have

X
dc(i) ≡ 0 (mod p).
i∈B1

From this, we conclude that, by multiplying by d−1

X
c(i) ≡ 0 (mod p),
i∈B1

for all p ∈ P. So we deduce that

X
c(i) = 0.
i∈B1

Similarly, for higher s, we find that for each base p colouring, we have
X X
pt dc(i) + xi c(i) ≡ 0 (mod pt+1 )
i∈Bs i∈B1 ∪...∪Bs

for all s ≥ 2, and some t dependent on s and p. Multiplying by d−1 , we find

X X
pt c(i) + (d−1 xi )c(i) ≡ 0 (mod pt+1 ). (∗)
i∈Bs i∈B1 ∪...∪Bs−1

We claim that this implies

X
c(i) ∈ hc(i) : i ∈ B1 ∪ · · · ∪ Bs−1 i.
i∈Bs

This is not exactly immediate, because the values of xi in (∗) may change as we
change our p. But it is still some easy linear algebra.
Suppose this were not true. Since we are living in a Euclidean space, we have
an inner product, and we can find some v ∈ Zm such that

hv, c(i) i = 0 for all i ∈ B1 ∪ · · · ∪ Bs−1 ,

and * +
X
v, c(i) 6= 0.
i∈Bs

But then, taking inner products with gives

* +
X
t (i)
p v, c ≡ 0 (mod pt+1 ).
i∈Bs

Equivalently, we have
* +
X
(i)
v, c ≡0 (mod p),
i∈Bs

but this is a contradiction. So we showed that A has the columns property with
respect to the partition [n] = B1 ∪ · · · ∪ Br .

33
3 Partition Regularity III Ramsey Theory

We now
prove the hard direction. We want an analogous gadget to our

1 λ −1 we had for the single-equation case. The definition will seem rather
mysterious, but it turns out to be what we want, and its purpose becomes more
clear as we look at some examples.
Definition ((m, p, c)-set). For m, p, c ∈ N, a set S ⊆ N is an (m, p, c)-set with
generators x1 , · · · , xm if S has the form
 
X m λi = 0 for all i < j 
S= λ i xi : λj = c .
λi ∈ [−p, p]
 
i=0

In other words, we have

m
[
S= {cxj + λj+1 xj+1 + · · · + λm xm : λi ∈ [−p, p]}.
j=1

For each j, the set {cxj + λj+1 xj+1 + · · · + λm xm : λi ∈ [−p, p]} is called a row
of S.
Example. What does a (2, p, 1) set look like? It has the form

{x1 − px2 , x1 − (p − 1)x2 , · · · , x1 + px2 } ∪ {x2 }.

In other words, this is just an arithmetic progression with its common difference.
Example. A (2, p, 3)-set has the form

{3x1 − px2 , · · · , 3x1 , · · · , 3x1 = px2 } ∪ {3x2 }.

The idea of an (m, p, c) set is that we “iterate” this process many times, and
so an (m, p, c)-set is an “iterated AP’s and various patterns of their common
differences”.
Our proof strategy is to show that that whenever we finitely-colour N, we can
always find an (m, p, c)-set, and given any matrix A with the columns property
and any (m, p, c)-set (for suitable m, p, c), there will always be a solution in
there.

Proposition. Let m, p, c ∈ N. Then whenever N is finitely coloured, there

exists a monochromatic (m, p, c)-set.
Proof. It suffices to find an (m, p, c)-set all of whose rows are monochromatic,
since when N is k-coloured, and (m0 , p, c)-set with m0 = mk + 1 has m monochro-
matic rows of the same colour by pigeonhole, and these rows contain a monochro-
matic (m, p, c)-set, by restricting to the elements where a lot of the λi are zero.
In this proof, whenever we say (m, p, c)-set, we mean one all of whose rows are
monochromatic.
We will prove this by induction. We have a k-colouring of [n], where n is
very very very large. This contains a k-colouring of
n jnk o
B = c, 2c, · · · , c .
c

34
3 Partition Regularity III Ramsey Theory

n
Since c is fixed, we can pick this so that c is large. By van der Waerden, we
find some set monochromatic

A = {cx1 − N d, cx1 − (N − 1)d, · · · , cx1 + N d} ⊆ B,

with N very very large. Since each element is a multiple of c by assumption,

we know that c | d. By induction, we may find an (m − 1, p, c)-set in the set
{d, 2d, · · · , M d}, where M is large. We are now done by the (m, p, c) set on
generators x1 , · · · , xn , provided
m
X
cx1 + λi xi ∈ A
i=2

for all λi ∈ [−p, p], which is easily seen to be the case, provided N ≥ (m −
1)pM .


Note that the argument itself is quite similar to that in the 1 λ −1 case.
Recall that Schur’s theorem said that whenever we finitely-colour N, we can
find a monochromatic {x, y, x + y}. More generally, for x1 , x2 , · · · , xm ∈ N, we
let ( )
X
F S(x1 , · · · , xm ) = xi : I ⊆ [n], I 6= ∅ .
i∈I

The existence of a monochromatic (m, 1, 1)-sets gives us

Corollary (Finite sum theorem). For every fixed m, whenever we finitely-colour
N, there exists x1 , · · · , xm such that F S(x1 , · · · , xm ) is monochromatic.
This is since an (m, 1, 1)-set contains more things than F S(x1 , · · · , xm ). This
was discovered independently by a bunch of different people, including Folkman,
Rado and Sanders.
Similarly, if we let
( )
Y
F P (x1 , · · · , xm ) = xi : I ⊆ [n], I 6= ∅ ,
i∈I

then we can find these as well. For example, we can restrict attention to
{2n : n ∈ N}, and use the finite sum theorem. This is the same idea as we had
when we used van der Waerden to find geometric progressions.
But what if we want both? Can we have F S(x1 , · · · , xm ) ∪ F P (x1 , · · · , xm )
in the same colour class? The answer is actually not known! Even the case
when m = 2, i.e. finding a monochromatic set of the form {x, y, x + y, xy} is
open. Until mid 2016, we did not know if we can find {x + y, xy} monochromatic
(x, y > 2).
To finish he proof of Rado’s theorem, we need the following proposition:
Proposition. If A is a rational matrix with the columns property, then there
is some m, p, c ∈ N such that Ax = 0 has a solution inside any (m, p, c) set, i.e.
all entries of the solution lie in the (m, p, c) set.
In the case of a single equation, we reduced the general problem to the case
of 3 variables only. Here we are going to do something similar — we will use the
columns property to reduce the solution to something much smaller.

35
3 Partition Regularity III Ramsey Theory

Proof. We again write

 
↑ ↑ ↑
A = c(1) c(2) ··· c(n)  .
↓ ↓ ↓

Re-ordering the columns of A if necessary, we assume that we have

[n] = B1 ∪ · · · ∪ Br

such that max(Bs ) < min(Bs+1 ) for all s, and we have

X X
c(i) = qis c(i)
i∈Bs i∈B1 ∪...∪Bs−1

for some qis ∈ Q. These qis only depend on the matrix. In other words, we have
X
dis c(i) = 0,

where 
−qis
 i ∈ B1 ∪ · · · Bs−1
dis = 1 i ∈ Bs

0 otherwise


For a fixed s, if we scan these coefficients starting from i = n and then keep
decreasing i, then the first non-zero coefficient we see is 1, which is good, because
it looks like what we see in an (m, p, c) set.
Now we try to write down a general solution with r many free variables.
Given x1 , · · · , xr ∈ Nr , we look at
r
X
yi = dis xs .
s=1

It is easy to check that Ay = 0 since

X XX X X
yi c(i) = dis xs c(i) = xs dis c(i) = 0.
i s s i

Now take m = r, and pick c large enough such that cdis ∈ Z for all i, s, and
finally, p = max{cdis : i, s ∈ Q}.
Thus, if we consider the (m, p, c)-set on generators (xm , · · · , x1 ) and yi as
defined above, then we have Ay = 0 and hence A(cy) = 0. Since cy is integral,
and lies in the (m, p, c) set, we are done!
We have thus proved Rado’s theorem.
Theorem (Rado’s theorem). A matrix A is partition regular iff it has the
column property.
So we have a complete characterization of all partition regular matrices.
Note that Rado’s theorem reduces Schur’s theorem, van der Waerden’s
theorem, finite sums theorem etc. to just checking if certain matrices have the
columns property, which are rather straightforward computations.
More interestingly, we can prove some less obvious “theoretical” results.

36
3 Partition Regularity III Ramsey Theory

Corollary (Consistency theorem). If A, B are partition regular in independent

variables, then  
A 0
0 B
is partition regular. In other words, we can solve Ax = 0 and By = 0 simultane-
ously in the same colour class.
Proof. The matrix  
A 0
0 B
has the columns property if A and B do.

In fact, much much more is true.

Corollary. Whenever N is finitely-coloured, one colour class contains solutions
to all partition regular systems!
Proof. Suppose not. Then we have N = D1 ∪ · · · ∪ Dk such that for each Di ,
there is some partition regular matrix Ai such that we cannot solve Ai x = 0
inside Di . But this contradicts the fact that diag(A1 , A2 , · · · , Ak ) is partition
regular (by applying consistency theorem many times).
Where did this whole idea of the (m, p, c)-sets come from? The original proof
by Rado didn’t use (m, p, c)-sets, and this idea only appeared only a while later,
when we tried to prove a more general result.
In general, we call a set D ⊆ N partition regular if we can solve any partition
regular system in D. Then we know that N, 2N are partition regular sets, but
2N + 1 is not (because we can’t solve x + y = z, say). Then what Rado’s theorem
says is that whenever we finitely partition N, then one piece of N is partition
regular.
In the 1930’s, Rado conjectured that there is nothing special about N to
begin with — whenever we break up a partition regular set, then one of the
pieces is partition regular. This conjecture was proved by Deuber in the 1970s
who introduced the idea of the (m, p, c)-set.
It is not hard to check that D is partition regular iff D contains an (m, p, c)
set of each size. Then Deuber’s proof involves showing that for all m, p, c, k ∈ N,
there exists n, q, d ∈ N such that any k-colouring of an (n, q, d)-set contains
a monochromatic (m, p, c) set. The proof is quite similar to how we found
(m, p, c)-sets in the naturals, but instead of using van der Waerden theorem, we
need the Hales–Jewett theorem.

We end by mentioning an open problem in this area. Suppose A is an m × n

matrix A that is not partition regular. That is, there is some k-colouring of N
with no solution to Ax = 0 in a colour class. Can we find some bound f (m, n),
such that every such A has a “bad” colouring with k < f (m, n)? This is an open
problem, first conjectured by Rado, and we think the answer is yes.
What do we actually know about this problem? The answer is trivially yes
for f (1, 2), as there aren’t many matrices of size 1 × 2, up to rescaling. It is a
non-trivial theorem that f (1, 3) exists, and in fact f (1, 3) ≤ 24. We don’t know
anything more than that.

37
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

4 Topological Dynamics in Ramsey Theory

Recall the finite sum theorem — for any fixed k, whenever N is finitely coloured,
we can find x1 , · · · , xk such that F S(x1 , x2 , · · · , xk ) is monochromatic. One
natural generalization is to ask the following question — can we find an infinite
set A such that
( )
X
F S(A) = x : B ⊆ A finite non-empty
x∈B

is monochromatic? The first thought upon hearing this question is probably

either “this is so strong that there is no way it can be true”, or “we can deduce
it easily, perhaps via some compactness argument, from the finite sum theorem”.
Both of these thoughts are wrong. It is true that it is always possible to find
these x1 , x2 , · · · , but the proof is hard. This is Hindman’s theorem.
The way we are going to approach this is via topological dynamics, which
is the title of this chapter. The idea is we construct a metric space (and in
particular a dynamical system) out of the Ramsey-theoretic problem we are
interested in, and then convert the Ramsey-theoretic problem into a question
about topological properties of the space we are constructed.
In the case of Hindman’s theorem, it turns out the “topological” form is a
general topological fact, which we can prove for a general dynamical system.
What is the advantage of this approach? When we construct the dynamical
system we are interested in, what we get is highly “non-geometric”. It would
be very difficult to think of it as an actual “space”. It is just something that
happens to satisfy the definition of a metric space. However, when we prove the
general topological facts, we will think of our metric space as a genuine space
like Rn , and this makes it much easier to visualize what is going on in the proofs.
A less obvious benefit of this approach is that we will apply Tychonoff’s
theorem many times, and also use the fact that the possibly infinite intersection
of nested compact sets is open. If we don’t formulate our problem in topological
terms, then we might find ourselves re-proving these repeatedly, which further
complicates the proof.
We now begin our journey.
Definition (Dynamical system). A dynamical system is a pair (X, T ) where X
is the compact metric space and T is a homeomorphism on X.
Example. (T = R/Z, Tα (x) = x + α) for α ∈ R is a dynamical system.
In this course, this is not the dynamical system we are interested in. In fact,
we are only ever going to be interested in one dynamical system.
We fix number of colours k ∈ N. Instead of looking at a particular colouring,
we consider the space of all k-colourings. We let

C = {c : Z → [k]} ∼
= [k]Z .
We endow this with the product topology. Since [k] has the discrete topology,
our basic open sets have the form

U = {c : Z → [k] : c(i1 ) = c1 , · · · , c(is ) = cs }

for some i1 , · · · , is ∈ Z and c1 , · · · , cs ∈ [k].

38
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

Since [k] is trivially compact, by Tychonoff’s theorem, we know that C is

compact. But we don’t really need Tychonoff, since we know that C is metrizable,
with metric
1
ρ(c1 , c2 ) = ,
n+1
where n is the largest integer for which c1 and c2 agree on [−n, n]. This metric
is easily seen to give rise to the same topology, and by hand, we can see this is
sequentially compact.
We now have to define the operation on C we are interested in.
Definition (Left shift). The left shift operator L : C → C is defined by

(Lc)(i) = c(i + 1).

We observe that this map is invertible, with inverse given by the right shift. This
is one good reason to work over Z instead of N. Moreover, we see that L is nice
and uniformly continuous, since if
1
ρ(c1 , c2 ) ≤ ,
n+1
then
1
ρ(Lc1 , Lc2 ) ≤ .
n
Similarly, L−1 is uniformly continuous. So it follows that (C, L) is a dynamical
system.
Instead of proving Hindman’s theorem directly, we begin by re-proving van
der Waerden’s theorem using this approach, to understand better how it works.
Theorem (Topological van der Waerden). Let (X, T ) be a dynamical system.
Then there exists an ε > 0 such that whenever r ∈ N, then we can find x ∈ X
and n ∈ N such that ρ(x, T in x) < ε for all i = 1, · · · , r.
In words, this says if we flow around X under T , then eventually some point
must go back near to itself, and must do that as many times as we wish to, in
regular intervals.
To justify calling this the topological van der Waerden theorem, we should
be able to easily deduce van der Waerden’s theorem from this. It is not difficult
to imagine this is vaguely related to van der Waerden in some sense, but it is
not obvious how we can actually do the deduction. After all, topological van
der Waerden theorem talks about the whole space of all colourings, and we do
not get to control what x we get back from it. What we want is to start with a
single colouring c and try to say something about this particular c.
Now of course, we cannot restrict to the sub-system consisting only of c itself,
because, apart from it being really silly, the function L does not restrict to a
map {c} → {c}. We might think of considering the set of all translates of c.
While this is indeed closed under L, this is not a dynamical system, since it is
not compact! The solution is to take the closure of that.
Definition (Orbital closure). Let (X, T ) be a dynamical system, and x ∈ X.
The orbital closure x̄ of x is the set cl{T s x : s ∈ Z}.

39
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

Observe that x̄ is a closed subset of a compact space, hence compact.

Proposition. (X̄, T ) is a dynamical system.
Proof. It suffices to show that x̄ is closed under T . If y ∈ x̄, then we have
some si such that T si x → y. Since T is continuous, we know T si +1 x → T y. So
T y ∈ x̄. Similarly, T −1 x̄ = x̄.
Once we notice that we can produce such a dynamical system from our
favorite point, it is straightforward to prove van der Waerden.
Corollary (van der Waerden theorem). Let r, k ∈ N. Then whenever Z is
k-coloured, then there is a monochromatic arithmetic progression of length r.
Proof. Let c : Z → [k]. Consider (c̄, L). By topological van der Waerden, we can
find x ∈ c̄ and n ∈ N such that ρ(x, Lin x) < 1 for all i = 1, · · · , r. In particular,
we know that x and Lin x agree at 0. So we know that

x(0) = Lin x(0) = x(in)

for all i = 0, · · · , r.
We are not quite done, because we just know that x ∈ c̄, and not that
x = Lk x for some k.
But this is not bad. Since x ∈ c̄, we can find some s ∈ Z such that
1
ρ(T s c, x) ≤ .
rn + 1
This means x and T s c agree on the first rn + 1 elements. So we know

c(s) = c(s + n) = · · · = c(s + rn).

Since we will be looking at these c̄ a lot, it is convenient to figure out what

this c̄ actually looks like. It turns out there is a reasonably good characterization
of these orbital closures.
Let’s look at some specific examples. Consider c given by

Then the orbital closure has just two points, c and Lc.
What if we instead had the following?

Then c̄ contains all translates of these, but also

,
We define the following:
Definition (Seq). Let c : Z → [k]. We define

Seq(c) = {(c(i), · · · , c(i + r)) : i ∈ Z, r ∈ N}.

It turns out these sequences tell us everything we want to know about orbital
closures.

40
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

Proposition. We have c0 ∈ c̄ iff Seq(c0 ) ⊆ Seq(c).

The proof is just following the definition and checking everything works.
Proof. We first prove ⇒. Suppose c0 ∈ c̄. Let (c0 (i), · · · , c0 (i + r − 1)) ∈ Seq(c).
Then we have s ∈ Z such that
1
ρ(c0 , Ls c) < ,
1 + max(|i|, |i + s − 1|)

which implies

(c(s + i), · · · , c(s + i + r − 1)) = (c0 (i), · · · , c0 (i + s − 1)).

So we are done.
For ⇐, if Seq(c0 ) ⊆ Seq(c), then for all n ∈ N, there exists sn ∈ Z such that

(c0 (−n), · · · , c0 (n)) = (c(sn − n), · · · , c(sn + n)).

Then we have
Lsi c → c0 .
So we have c0 ∈ c̄.
We now return to talking about topological dynamics. We saw that in our
last example, the orbital closure of c has three “kinds” of things — translates of
c, and the all-red and all-blue ones. The all-red and all-blue ones are different,
because they seem to have “lost” the information of c. In fact, the orbital closure
of each of them is just that colouring itself. This is a strict subset of c̄. These
are phenomena we don’t want.
Definition (Minimal dynamical system). We say (X, T ) is minimal if x̄ = X
for all x ∈ X. We say x ∈ X is minimal if (x̄, T ) is a minimal dynamical system.
Proposition. Every dynamical system (X, T ) has a minimal point.
Thus, most of the time, when we want to prove something about dynamical
systems, we can just pass to a minimal subsystem, and work with it.
Proof. Let U = {x̄ : x ∈ X}. Thus is a family of closed sets, ordered by inclusion.
We want to apply Zorn’s lemma to obtain a minimal element. Consider a chain
S in U. If
x̄1 ⊇ x̄2 ⊇ · · · ⊇ x̄n ,
then their intersection is x̄n , which is in particular non-empty. So any finite
collection in S has non-empty intersection. Since X is compact, we know
\
x̄ 6= ∅.
x̄∈S

We pick \
z∈ x̄ 6= ∅.
x̄∈S

Then we know that

z̄ ⊆ x̄

41
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

for all x̄ ∈ S. So we know \

z̄ ⊆ x̄ 6= ∅.
x̄∈S

So by Zorn’s lemma, we can find a minimal element (in both senses).

Example. Consider c given by

Then we saw that c̄ contains all translates of these, and also

,
Then this system is not minimal, since the orbital closure of the all-red one is a
strict subsystem of c̄.
We are now going to derive some nice properties of minimal systems.
Lemma. If (X, T ) is a minimal system, then for all ε > 0, there is some m ∈ N
such that for all x, y ∈ X, we have

min ρ(T s x, y) < ε.

|s|≤m

Proof. Suppose not. Then there exists ε > 0 and points xi , yi ∈ X such that

min ρ(T s xi , yi ) ≥ ε.
|s|≤i

By compactness, we may pass to subsequences, and assume xi → x and yi → y.

By continuity, it follows that

ρ(T s x, y) ≥ ε

for all s ∈ Z. This is a contradiction, since x̄ = X by minimality.

We now want to prove topological van der Waerden.
Theorem (Topological van der Waerden). Let (X, T ) be a dynamical system.
Then there exists an ε > 0 such that whenever r ∈ N, then we can find x ∈ X
and n ∈ N such that ρ(x, T in x) < ε for all i = 1, · · · , r.
Proof. Without loss of generality, we may assume (X, T ) is a minimal system.
We induct on r. If r = 1, we can just choose y ∈ X, and consider T y, T 2 y, · · · .
Then note that by compactness, we have s1 , s2 ∈ N such that

ρ(T s1 y, T s2 y) < ε,

and then take x = T s1 y and n = s2 − s1 .

Now suppose the result is true for r > 1, and that we have the result for all
ε > 0 and r − 1.
Claim. For all ε > 0, there is some point y ∈ X such that there is an x ∈ X
and n ∈ N such that
ρ(tin x, y) < ε
for all 1 ≤ i ≤ r.

42
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

Note that this is a different statement from the theorem, because we are not
starting at x. In fact, this is a triviality. Indeed, let (x0 , n) be as guaranteed by
the hypothesis. That is, ρ(x0 , T in x0 ) < ε for all 1 ≤ i ≤ r. Then pick y = x0
and x = T −n x0 .
The next goal is to show that there is nothing special about this y.
Claim. For all ε > 0 and for all z ∈ X, there exists xz ∈ X and n ∈ N for
which ρ(T in xz , z) < ε.
The idea is just to shift the picture so that y gets close to z, and see where
we send x to. We will use continuity to make sure we don’t get too far away.
We choose m as in the previous lemma for 2ε . Since T −m , T −m+1 , · · · , T m
are all uniformly continuous, we can choose ε0 such that ρ(a, b) < ε0 implies
ρ(T s a, T s b) < 2ε for all |s| ≤ m.
Given z ∈ X, we obtain x and y by applying our first claim to ε0 . Then we
can find s ∈ Z with |s| ≤ m such that ρ(T s y, z) < 2ε . Consider xz = T s x. Then

ρ(T in xz , z) ≤ ρ(T in xz , T s y) + ρ(T s y, z)

ε
≤ ρ(T s (T in x), T s y) +
2
ε ε
≤ +
2 2
=ε

Claim. For all ε > 0 and z ∈ X, there exists x ∈ X, n ∈ N and ε0 > 0 such
that T in (B(x, ε0 )) ⊆ B(z, ε) for all 1 ≤ i ≤ r.
We choose ε0 by continuity, using the previous claim.

The idea is that we repeatedly apply the final claim, and then as we keep
moving back, eventually two points will be next to each other.
We pick z0 ∈ X and set ε0 = 2ε . By the final claim, there exists z1 ∈ X and
some n1 ∈ N such that T in1 (B(z1 , ε1 )) ⊆ B(z0 , ε0 ) for some 0 < ε1 ≤ ε0 and all
1 ≤ i ≤ r.
Inductively, we find zs ∈ X, ns ∈ N and some 0 < εs ≤ εs−1 such that

T ins (B(zs , εs )) ⊆ B(zs−1 , εs−1 )

for all 1 ≤ i ≤ r.
By compactness, (zs ) has a convergent subsequence, and in particular, there
exists i < j ∈ N such that ρ(zi , zj ) < 2ε .
Now take x = zj , and

n = nj + nj−1 + · · · + ni+1

Then
T `n (B(x, εj )) ⊆ B(zi , εi ).
for all 1 ≤ ` ≤ r. But we know
ε
ρ(zi , zj ) ≤ ,
2
and
ε
εi ≤ ε0 ≤ .
2

43
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

So we have
ρ(T `n x, x) ≤ ε
for all 1 ≤ ` ≤ r.
In the remaining of the chapter, we will actually prove Hindman’s theorem.
We will again first prove a “topological” version, but unlike the topological van
der Waerden theorem, it will look nothing like the actually Hindman’s theorem.
So we still need to do some work to deduce the actual version from the topological
version.
To state topological Hindman, we need the following definition:
Definition (Proximal points). We say x, y ∈ X are proximal if

inf ρ(T s x, T s y) = 0.
s∈Z

Example. Two colourings c1 , c2 ∈ C are proximal iff there are arbitrarily large
intervals where they agree.

The topological form of Hindman’s theorem says the following:

Theorem (Topological Hindman’s theorem). Let (X, T ) be a dynamical system,
and suppose X = x̄ for some x ∈ X. Then for any minimal subsystem Y ⊆ X,
then there is some y ∈ Y such that x and y are proximal.

We will first show how this implies Hindman’s theorem, and then prove this.
To do the translation, we need to, of course, translate concepts in dynamical
systems to concepts about colourings. We previously showed that for colourings
c, c0 , we have c0 ∈ c̄ iff Seq(c0 ) ⊆ Seq(c). The next thing to figure out is when
c : Z → [k] is minimal. By definition, this means for any x ∈ c̄, we have x̄ = c̄.
Equivalently, we have Seq(x) = Seq(c).
We introduce some notation.
Notation. For an interval I ⊆ Z, we say I = {a, a + 1, · · · , b}, we write c(I) for
the sequence (c(a), c(a + 1), · · · , c(b)).
Clearly, we have

Seq(c) = {c(I) : I ⊆ Z is an interval}.

We say for intervals I1 , I2 ⊆ Z, we have c(I1 ) 4 c(I2 ), if c(I1 ) is a subsequence

of c(I2 ).
Definition (Bounded gaps property). We say a colouring c : Z → [k] has the
bounded gaps property if for each interval I ⊆ Z, there exists some M > 0 such
that c(I) 4 c(U) for every interval U ⊆ Z of length at least M .
For example, every periodic colouring has the bounded gaps property.
It turns out this is precisely what we need to characterize minimal colourings.

Proposition. A colouring c : Z → [k] is minimal iff c has the bounded gaps

property.

44
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

Proof. Suppose c has the bounded gaps property. We want to show that for all
x ∈ c̄, we have Seq(x) = Seq(c). We certainly got one containment Seq(x) ⊆
Seq(c). Consider any interval I ⊆ Z. We want to show that c(I) ∈ Seq(x). By
the bounded gaps property, there is some M such that any interval U ⊆ Z of
length > M satisfies c(I) 4 c(U). But since x ∈ c̄, we know that

x([0, · · · , M ]) = c([t, t + 1, · · · , t + M ])

for some t ∈ Z. So c(I) 4 x([0, · · · , M ]), and this implies Seq(c) ⊆ Seq(x).
For the other direction, suppose c does not have the bounded gaps property.
So there is some bad interval I ⊆ Z. Then for any n ∈ N, there is some tn such
that
c(I) 64 c([tn − n, tn − n + 1, · · · , tn + n]).
Now consider xn = Ltn (c). By passing to a subsequence if necessary, we may
assume that xn → x. Clearly, c(I) 6∈ Seq(x). So we have found something in
Seq(c) \ Seq(x). So c 6∈ x̄.
It turns out once we have equated minimality with the bounded gaps property,
it is not hard to deduce Hindman’s theorem.
Theorem (Hindman’s theorem). If c : N → [k] is a k-colouring, then there
exists an infinite A ⊆ N such that F S(A) is monochromatic.
Proof. We extend the colouring c to a colouring of Z by defining x : Z → [k + 1]
with
x(i) = x(−i) = c(i)
if x 6= 0, and x(0) = k + 1. Then it suffices to find an infinite an infinite A ⊆ Z
such that F S(A) is monochromatic with respect to x.
We apply topological Hindman to (x̄, L) to find a minimal colouring y such
that x and y are proximal. Then either

inf ρ(Ln x, Ln y) = 0 or inf ρ(L−n x, L−n y) = 0.

n∈N n∈N

We wlog it is the first case, i.e. x and y are positively proximal. We now build
up this infinite set A we want one by one.
Let the colour of y(0) be red. We shall in fact pick 0 < a1 < a2 < · · ·
inductively so that x(t) = y(t) = red for all t ∈ F S(a1 , a2 , · · · ).
By the bounded gaps property of y, there exists some M1 such that for any
I ⊆ Z of length ≥ M1 , then it contains y([0]), i.e. y([0]) 4 y(I).
Since x and y are positively proximal, there exists I ⊆ Z such that |I| ≥ M
and min(I) > 0 such that x(I) = y(I). Then we pick a1 ∈ I such that
x(a1 ) = y(a1 ) = y(0).
Now we just have to keep doing this. Suppose we have found a1 < · · · < an
as required. Consider the interval J = [0, · · · , a1 + a2 + · · · + an ]. Again by
the bounded gaps property, there exists some Mn+1 such that if I ⊆ Z has
|I| ≥ Mn+1 , then y(J) 4 y(I).
We choose an interval I ⊆ Z such that
(i) x(I) = y(I)

(ii) |I| ≥ Mn+1

45
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

Pn
(iii) min I > i=1 ai .
Then we know that

y([0, · · · , a1 + · · · + an ]) 4 y(I).

Let an+1 denote by the position at which y([0, · · · , a1 + · · · + an ]) occurs in y(I).

It is then immediate that x(z) = y(z) = red for all z ∈ F S(a1 , · · · , an+1 ), as any
element in F S(a1 , · · · , an+1 ) is either

– t0 for some t0 ∈ F S(a1 , . . . , an );

– an+1 ; or
– an+1 + t0 for some t0 ∈ F S(a1 , · · · , an ),
and these are all red by construction.
Then A = {a1 , a2 , · · · } is the required set.
The heart of the proof is that we used topological Hindman to obtain a
minimal proximal point, and this is why we can iteratively get the an .
It remains to prove topological Hindman.

Theorem (Topological Hindman’s theorem). If (X, T ) is a dynamical system,

X = x̄ and Y ⊆ X is minimal, then there exists y ∈ Y such that x and y are
proximal.
This is a long proof, and we will leave out proofs of basic topological facts.
Proof. If X is a compact metric space, then X X = {f : X → X} is compact
under the product topology by Tychonoff. The basic open sets are of the form

{f : X → Y | f (xi ) ∈ Ui for i = 1, · · · , k}

for some fixed xi ∈ X and Ui ⊆ X open.

Now any function g : X → X can act on X X in two obvious ways —

– Post-composition Lg : X X → X X be given by Lg (f ) = g ◦ f .
– Pre-composition Rg : X X → X X be given by Rg (f ) = f ◦ g.
The useful thing to observe is that Rg is always continuous, while Lg is continuous
if g is continuous.
Now if (X, T ) is a dynamical system, we let

ET = cl{T s : s ∈ Z} ⊆ X X .

The idea is that we look at what is going on in this space instead. Let’s note a
few things about this subspace ET .

– ET is compact, as it is a closed subset of a compact set.

– f ∈ ET iff for all ε > 0 and points x1 , · · · , xk ∈ X, there exists s ∈ Z such
that ρ(f (xi ), T s (xi )) < ε.
– ET is closed under composition.

46
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

So in fact, ET is a compact semi-group inside X X . It turns out every proof of

Hindman’s theorem involves working with a semi-group-like object, and then
trying to find an idempotent element.
Theorem (Idempotent theorem). If E ⊆ X X is a compact semi-group, then
there exists g ∈ E such that g 2 = g.
This is a strange thing to try to prove, but it turns out once we came up
with this statement, it is not hard to prove. The hard part is figuring out this is
the thing we want to prove.
Proof. Let F denote the collection of all compact semi-groups of E. Let A ∈ F
be minimal with respect to inclusion. To see A exists, it suffices (by Zorn) to
check that any chain S in F has a lower bound in F, but this is immediate,
since the intersection of nested compact sets is noon-empty.
Claim. Ag = A for all g ∈ A.
We first observe that Ag is compact since Rg is continuous. Also, Ag is a
semigroup, since if f1 g, f2 g ∈ Ag, then

f1 gf2 g = (f1 gf2 )g ∈ Ag .

Finally, since g ∈ A, we have Ag ⊆ A. So by minimality, we have Ag = A.

Now let
Bg = {f ∈ A : f g = g}.
Claim. Bg = A for all g ∈ A.
Note that Bg is non-empty, because Ag = A. Moreover, B is closed, as B is
the inverse of {g} under Rg . So B is compact. Finally, it is clear that B is a
semi-group. So by minimality, we have Bg = A.
So pick any g ∈ A, and then g 2 = g.
Proof of topological Hindman (continued). We are actually going to work in a
slightly smaller compact semigroup than ET . We let F ⊆ ET be defined by

F = {f ∈ ET : f (x) ∈ Y }.

Claim. F ⊆ X X is a compact semigroup.

Before we prove the claim, we see why it makes sense to consider this F.
Suppose the claim is true. Then by applying the idempotent theorem, to get
g ∈ F such that g 2 = g. We now check that x, g(x) are proximal.
Since g ∈ F ⊆ ET , we know for all ε, there exists s ∈ Z such that
ε ε
ρ(g(x), T s (x)) < , ρ(g(g(x)), T s (g(x))) < .
2 2
But we are done, since g(x) = g(g(x)), and then we conclude from the triangle
inequality that
ρ(T s (x), T s (g(x))) < ε.
So x and g(x) ∈ Y are proximal.
It now remains to prove the final claim. We first note that F is non-empty.
Indeed, pick any y ∈ Y . Since X = x̄, there exists some sequence T ni (x) → y.

47
4 Topological Dynamics in Ramsey Theory III Ramsey Theory

Now by compactness of ET , we can find some f ∈ ET such that (T ni )i≥0 cluster

at f , i.e. every open neighbourhood of f contains infinitely many T ni . Then
since X is Hausdorff, it follows that f (x) = y. So f ∈ F.
To show F is compact, it suffices to show that it is closed. But since Y = ȳ
for all y ∈ Y by minimality, we know Y is in particular closed, and so F is closed
in the product topology.
Finally, we have to show that F is closed under composition, so that it is a
semi-group. To show this, it suffices to show that any map f ∈ ET sends Y to
Y . Indeed, by minimality of Y , this is true for T s for s ∈ Z, and then we are
done since Y is closed.
The actual hard part of the proof is deciding we should prove the idempotent
theorem. It is not an obvious thing to try!

48
5 Sums and products* III Ramsey Theory

5 Sums and products*

The goal of this final (non-examinable) chapter is to prove the following theorem:
Theorem (Moreira, 2016). If N is k-coloured, then there exists infinitely many
x, y such that {x, x + y, xy} is monochromatic.
This is a rather hard theorem, but the proof is completely elementary, and
just involves a very clever use of van der Waerden’s theorem. One of the main
ideas is to consider syndetic sets.
Definition (Syndetic set). We say A = {a1 < a2 < · · · } ⊆ N is syndetic if it
has bounded gaps, i.e. ai+1 − ai < b for all i.
It turns out these sets contain a lot of structure. What happens when we
finitely colour a syndetic set? Are we guaranteed to have a monochromatic
syndetic set? Let’s take the simplest syndetic set — N. Let’s say we 2-colour N.
Does one of the classes have to by syndetic? Of course not. For example, we
can look at this:
···

But this set obviously has some very nice structure. So we are motivated to
consider the following definition:

Definition (Piecewise syndetic set). We say A ⊆ N is piecewise syndetic if there

exists b > 0 such that A has gaps bounded by b on arbitrarily long intervals.
More explicitly, if we again write A = {a1 < a2 < · · · }, then there exists b
such that for all N > 0, there is i ∈ N such that ak+1 −ak < b for k = i, · · · , i+N .
We begin with two propositions which are standard results.

Proposition. If A is piecewise syndetic and A = X ∪ Y , then one of X and Y

is piecewise syndetic.
Proof. We fix b > 0 and the sequence of intervals I1 , I2 , · · · with |In | ≥ n such
that A has gaps ≤ b in each In . We may, of course, wlog In are disjoint.
Each element in In is either in X or not. We let tn denote the largest
number of consecutive things in In that are in X. If tn is unbounded, then X is
piecewise syndetic. If tn ≤ K, then Y is piecewise syndetic, with gaps bounded
by (K + 1)b.
Of course, this can be iterated to any finite partition. There is nothing clever
so far.
Our next proposition is going to be a re-statement of van der Waerden’s
theorem in the world of piecewise syndetic sets.
Proposition. Let A ⊆ N be piecewise syndetic. Then for all m ∈ N, there
exists d ∈ N such that the set

A∗ = {x ∈ N : x, x + d, · · · , x + md ∈ A}.

is piecewise syndetic.

49
5 Sums and products* III Ramsey Theory

Proof. Let’s in fact assume that A is syndetic, with gaps bounded by b. The
proof for a piecewise syndetic set is similar, but we have to pass to longer and
longer intervals, and then piece them back together.
We want to apply van der Waerden’s theorem. By definition,

N = A ∪ (A + 1) ∪ · · · ∪ (A + b).

Let c : N → {0, · · · , b} by given by

c(x) = min{i : x ∈ A + i}.

Then by van der Waerden, we can find some a1 , d1 such that

a1 , a1 + d1 , · · · , a1 + md1 ∈ A + i.

Of course, this is equivalent to

(a1 − i), (a1 + i) + d1 , · · · , (a1 − i) + md1 ∈ A.

So we wlog i = 0.
But van der Waerden doesn’t require the whole set of N. We can split N into
huge blocks of size W (m + 1, b + 1), and then we run the same argument in each
of these blocks. So we find (a1 , d1 ), (a2 , d2 ), · · · such that

ai , ai + di , · · · , ai + mdi ∈ A.

Moreover, Ã = {a1 , a2 , · · · } is syndetic with gaps bounded by W (m + 1, b + 1).

But we need a fixed d that works for everything.
We now observe that by construction, we must have di ≤ W (m + 1, b + 1)
for all i. So this induces a finite colouring on the ai , where the colour of ai is
just di . Now we are done by the previous proposition, which tells us one of the
partitions must be piecewise syndetic.
That was the preliminary work we had to do to prove the theorem. The
proof will look very magical, and things only start to make sense as we reach the
end. This is not a deficiency of the proof. There is some reason this problem
was open for more than 40 years.
The original proof (arxiv:1605.01469) is a bit less magical, and used concepts
from topological dynamics. Interested people can find the original paper to read.
However, we will sacrifice “deep understanding” for having a more elementary
proof that just uses van der Waerden.
Proof of theorem. Let N = C1 ∪ · · · ∪ Cr . We build the following sequences:
(i) y1 , y2 , · · · ∈ N;
(ii) B0 , B1 , · · · and D1 , D2 , · · · which are piecewise syndetic sets;

(iii) t0 , t1 , · · · ∈ [r] which are colours.

We will pick these such that Bi ⊆ Cti .
We first observe that one of the colour classes Ci is piecewise syndetic. We
pick t0 ∈ [r] be such that Ct0 is piecewise syndetic, and pick B0 = Ct0 . We want

50
5 Sums and products* III Ramsey Theory

to apply the previous proposition to obtain D0 from B0 . We pick m = 2, and

then we can find a y1 such that
D1 = {z | z, z + y1 ∈ B0 }
is piecewise syndetic.
We now want to get B1 . We notice that y1 D1 is also piecewise syndetic, just
with a bigger gap. So there is a colour class t1 ∈ [r] such that y1 D1 ∩ Ct1 is
piecewise syndetic, and we let B1 = y1 D1 ∩ Ct1 .
In general, having constructed y1 , · · · , yi−1 ; B0 , · · · , Bi−1 ; D1 , · · · , Di−1 and
t0 , . . . , ti−1 , we proceed in the following magical way:
We apply the previous proposition with the really large m = y12 y22 · · · yi−1 2
to
find yi ∈ N such that the set
Di = {z | z, z + yi , · · · , z + (y12 y22 · · · yi−1
2
)yi ∈ Bi−1 }
is piecewise syndetic. The main thing is that we are not using all points in this
progression, but are just using some important points in there. In particular, we
use the fact that
z, z + yi , z + (yj2 · · · yi−1
2
)yi ∈ Bi−1
for all 1 ≤ j ≤ i − 1. It turns out these squares are important.
We have now picked yi and Di , but we still have to pick Bi . But this is just
the same as what we did. We know that yi Di is piecewise syndetic. So we know
there is some ti ∈ [r] such that Bi = yi Di ∩ Cti is piecewise syndetic.
Let’s write down some properties of these Bi ’s. Clearly, Bi ⊆ Cti , but we
can say much more. We know that
Bi ⊆ yi Bi−1 ⊆ · · · ⊆ yi yi−1 · · · yj+1 Bj .
Of course, there exists some tj , ti with j < i such that tj = ti . We set
y = yi yi−1 · · · yj+1 .
Let’s choose any z ∈ Bi . Then we can find some x ∈ Bj such that
z = xy,
We want to check that this gives us what we want. By construction, we have
x ∈ Bj ⊆ Cti , xy = z ∈ Bi ⊆ Cti .
So they have the same colour.
How do we figure out the colour of x + y? Consider
y(x + y) = z + y 2 ∈ yi Di + y 2 .
By definition, if a ∈ Di , then we know
2 2
a + (yj+1 · · · yi−1 )yi ∈ Bi−1 .
So we have
2 2 2 2
Di ⊆ Bi−1 − (yj+1 · · · yi+1 )yi ⊆ yj+1 · · · yi−1 Bj − (yj+1 · · · yi−1 )yi
So it follows that
y(x + y) ⊆ yi (yi−1 · · · yj+1 )Bj − y 2 + y 2 = yBj .
So x + y ∈ Bj ⊆ Ctj = Cti . So {x, x + y, xy} have the same colour.

51
Index III Ramsey Theory

Index

(m, p, c)-set, 34 higher dimensional canonical

Cn , 11 Ramsey theorem, 10
Pn , 10 Hindman’s theorem, 45
R(G, H), 17 topological, 44
R(Kn ), 11 homothetic copy, 20
R(Kn , Km ), 13
R(n), 11 idempotent theorem, 47
R(n, m), 13
Vn , 11 left shift, 39
X (r) , 5
minimal dynamical system, 41
[n], 5
monochromatic set, 5
N, 5
Seq, 40 off-diagonal Ramsey number, 13
L, 39 orbital closure, 39
k-colouring, 5
r-sets, 5 partition regular, 27
path graph, 10
active coordinates, 21 piecewise syndetic set, 49
bounded gaps property, 44 product argument, 20
proximal points, 44
canonical Ramsey theorem, 8
colour focused lines, 22 Rado’s theorem, 29, 36
colour focused progression, 19 Ramsey number, 11
colouring, 5 off-diagonal, 13
columns property, 28 Ramsey theorem
combinatorial line, 21 canonical, 8
complete graph, 11 higher dimensional, canonical,
consistency theorem, 37 10
Ramsey’s theorem, 6
density, 23 for r sets, 7
dynamical system, 38
minimal, 41 Schur’s theorem, 27
syndetic
finite Ramsey theorem, 11 piecewise, 49
Finite sum theorem, 35 syndetic set, 49
focus progression Szemerédi theorem, 23
colour, 19
focused lines, 22 topological Hindman’s theorem, 44,
colour, 22 46
focused progression, 19 topological van der Waerden
theorem, 39, 42
graph, 5
van der Waerden theorem, 18, 40
Hales–Jewett theorem, 21 topological, 39, 42

52