0Introduction
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.
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.