This is just some stuff I've been looking at recently.
In this blog post, we will discuss the powerful Hales-Jewett theorem, one of the central results of Ramsey theory. We use it to prove the famous van der Waerden theorem, as well as its
-dimensional generalisation, Gallai's theorem.
1. Definitions and Examples
For any positive integer
, we write
. Given a finite set
, we denote by

the
-dimensional hypercube on the alphabet
; that is, the set of all possible
-tuples
, with
.
A
-colouring of

is a map
; that is, we assign each element of

one of

colours, labelled by the elements of
.
A subset

of

is called a
combinatorial line if there exists a non-empty set of indices
![$I=\{i_1,i_2,\dots,i_k\}\subseteq[n]$](//latex.artofproblemsolving.com/2/6/a/26a4dd72743c2c7a1b8da7ac9549ed12166cb20f.png)
and, for each
, an

such that

We call

the set of
active coordinates of
, since these are the coordinates that vary: the others are "fixed". More informally, a combinatorial line is the set of
-tuples we get when we fix the values of some of the components, and set the other components equal to each other, allowing this common value to vary among the elements of
.
For example, in
, we have the following combinatorial lines:

Displayed more pictorially,
![[asy]
unitsize(1cm);
real e = 0.5;
for (int x=0; x<=2; ++x) {
for (int y=0; y<=2; ++y) {
label("$("+string(3-y)+","+string(x+1)+")$",(x,y));
}
}
DPA((-e,2)--(2+e,2)^^(-e,1)--(2+e,1)^^(-e,0)--(2+e,0),red);
DPA((0,-e)--(0,2+e)^^(1,-e)--(1,2+e)^^(2,-e)--(2,2+e),blue);
DPA((-e,2+e)--(2+e,-e),green);
[/asy]](//latex.artofproblemsolving.com/7/e/9/7e9f459fa7d9b7d81c5d10db2d6a7d918f6693d9.png)
Visual representations of combinatorial lines can be good when
; however, for
, I find them less useful, essentially because I struggle to visualise in

or more dimensions

.
Consider the standard "product order" on
, given by

for all
. If we restrict our attention to a combinatorial line, this partial order

is in fact a total order. Thus given a combinatorial line
, we define

to be the last element in our ordering of

and

to be the first element.
Given a
-colouring of
![$[m]^n$](//latex.artofproblemsolving.com/a/7/2/a721b3fb78fd06ec079fe6ea3ed0240f65c5ca77.png)
and a positive integer
, a
rainbow
-windmill is a set of

combinatorial lines

such that
- There exists
such that
for all
. We call
the focus of the rainbow
-windmill.
- Each individual
is monochromatic; i.e. all the points of an
, ignoring the focus, are the same colour.
- No two
have the same colour.
Finally, we introduce a definition needed for Gallai's theorem. Given a finite set
, a
homothetic copy of

is a set of the form
, where

and
. Geometrically, we are enlarging the set

by a positive integer scale factor from the origin, then translating the enlarged image by some vector in
. As an example, when
, a homothetic copy of
![$[m]$](//latex.artofproblemsolving.com/6/d/8/6d823912054b318ac7c77ee09ae9dcf0245ccc8d.png)
is an arithmetic progression of length
.
2. The Theorem
We are now ready to state the main result of this post.
Theorem. [Hales-Jewett] Given
, there exists

such that for any
-colouring of
, there is a monochromatic combinatorial line.
The smallest such

with the desired property is denoted by
.
Proof. We go by induction on
; the base case

is trivial. Now consider the following claim:
Claim. For
, there exists

such that for any
-colouring of
, there is either a monochromatic combinatorial line or a rainbow
-windmill.
Note that our theorem follows from this claim: take
, and look at the colour of the focus of the rainbow
-windmill.
We prove our claim by induction on
. For the base case
, take
. Now assume that

works for
; we show that
, where
, works for
.
Suppose that we have
-coloured
![$[m]^{n+d}$](//latex.artofproblemsolving.com/0/5/6/056ff1482ef1ab167ea3282cc4e633ad79ce9748.png)
such that there are no monochromatic combinatorial lines. Note that
![$[m]^{n+d}$](//latex.artofproblemsolving.com/0/5/6/056ff1482ef1ab167ea3282cc4e633ad79ce9748.png)
is isomorphic to
. There are

possible
-colourings of
, so by our choice of
, there is a (monochromatic) combinatorial line

in
, with active coordinate set
, such that for any
![$a\in[m]^n$](//latex.artofproblemsolving.com/2/b/d/2bd11a029604dccaee3e6b0b6e2033078d6d1dd5.png)
and
, the colour of

in our
-colouring of
![$[m]^{n+d}$](//latex.artofproblemsolving.com/0/5/6/056ff1482ef1ab167ea3282cc4e633ad79ce9748.png)
is the same as the color of

in the
-colouring of
.
Now take a rainbow
-windmill

for our
-colouring of
. Suppose the respective active coordinate sets are
, and let

be the focus. For each
, let

be the combinatorial line through the point

and with active coordinate set
. Then

is a rainbow
-windmill with focus
. Combining this with the combinatorial line through the point

with active coordinate set

gives us the desired rainbow
-windmill.
This completes the proof of the claim, and hence of the theorem.
3. Applications
We now see how the Hales-Jewett theorem can be used to prove van der Waerden's theorem and Gallai's theorem easily.
Theorem. [van der Waerden] Given
, there exists

such that for any
-colouring of
, there is a monochromatic arithmetic progression of length
.
Proof. Given a
-colouring

of
, consider the
-colouring

of
, with

sufficiently large, given by

By the Hales-Jewett theorem, there is a monochromatic combinatorial line in
, which corresponds to an arithmetic progression of length

in
. Explicitly, if

is the set of active coordinates of our combinatorial line, then our arithmetic progression is

where
.
Gallai's theorem is essentially a generalisation of van der Waerden's theorem to
. Recall that a homothetic copy of

is a set of the form
, where

and
.
Theorem. [Gallai] Given a finite set
, for any
-colouring of
, there exists a monochromatic homothetic copy of
.
Proof. Let
. Given a
-colouring

of
, consider the
-colouring

of
, with

sufficiently large, given by

By the Hales-Jewett theorem, there is a monochromatic combinatorial line in
, which corresponds to a monochromatic homothetic copy of

in
. Explicitly, if

is the set of active coordinates of our combinatorial line, then our homothetic copy of

is
. 