Proof. Pick $a_1\in \mathbb{N}$. Then there exists an infinite set $A_1$ such that $c(a_{1}i)=c_1$ for all $i\in A_1$. Pick $a_2\in A_1$ and find $A_2$ (infinite) such that $c(a_{2}i)=c_2$ for all $i\in A_2$. Keep on doing this. We end up with $a_1<a_2<a_3<\cdots <a_k<\cdots$ and $A_1\supset A_2\supset \cdots$ such that $c(a_{i}j)=c_i$ for all $j\in A_i$.

One colour appears infinitely many times $c_{i_1}=c_{i_2}=\cdots =c_{i_k}=\cdots =e$. Now note $M=\{a_{i_1},a_{i_2},a_{i_3},\dots \}$ is a monochromatic set. □

Proof. $r=1$ pigeonhole, $r=2$ is Theorem 1.1. Prove this by induction.

Assume it is true for $r-1$. Given $c:{\mathbb{N}}^{(r)}\to [k]$, we must find $M$ (infinite and monochromatic). Pick $a_1\in \mathbb{N}$. Look at the $r-1$ sets of $\mathbb{N}\setminus \{a_1\}$. Define $c^{\prime }:{(\mathbb{N}\setminus \{a_1\})}^{(r-1)}\to [k]$ via $c^{\prime }(F)=c(F\cup \{a_1\})$.

By induction there exists $A_1\subseteq \mathbb{N}\setminus \{a_1\}$ such that $c^{\prime }$ is constant on it, say constantly equal to $c_1$.

Now pick $a_2\in A_1$ and induce $c^{\prime }:{(A_1\setminus \{a_2\})}^{(r-1)}\to [k]$ defined by $c^{\prime }(F)=c(F\cup \{a_2\})$. By induction there exists $A_2\subset A_1\setminus \{a_2\}$ such that $c^{\prime }$ is constant on it, say equal to $c_2$.

Continuing this, we end up with $a_1,a_2,\dots$ and sets $A_1,A_2,\dots$ such that $A_{i+1}\subset A_i\setminus \{a_{i+1}\}$ with $c(F\cup \{a_i\})=c_i$ for all $F\subset A_{i+1}$, $|F|=r-1$.

Some colour must appear infinitely many times: say $c_{i_1}=c_{i_2}=c_{i_3}=\cdots =c$. Check: $M=\{a_{i_1},a_{i_2},\dots \}$ is monochromatic. □

Proof. Suppose not. Then for each $n$ we can find $c_n:{[n]}^{(r)}\to [k]$ with no monochromatic $m$-sets. Note that there are only finitely many ways to $k$-colour ${[r]}^{(r)}$. So infinitely many $c_n$ will agree on ${[r]}^{(r)}$. Pick $A_1$ such that for all $n\in A_1$,

We can do the same on ${[r+1]}^{(r)}$ and produce some $A_2\subset A_1$ such that $c_n{|}_{{[r+1]}^{(r)}}$ is constant on $A_2$.

Continuing this, we get $\cdots \subset A_n\subset A_{n-1}\subset \cdots \subset A_1$. They satisfy:

• (1) There is no monochromatic $m$-set for any $d_n:{[n]}^{(r)}\to [k]$ (because $d_n=c_i{|}_{{[n]}^{(r)}}$).
• (2) These $d_n$’s are nested: $d_j{|}_{{[i]}^{(r)}}=d_i$ for $j>i$.

Finally: colour ${\mathbb{N}}^{(r)}$ via $c(F)=d_n(F)$, where $n$ is any integer $n\ge \max F$. One can see that this is well defined, and gives a contradiction to Theorem 1.2. □

Proof. We colour an element $\{i<j<k<l\}$ of ${\mathbb{N}}^{(4)}$ as follows: We say that it is red if $c(ij)=c(kl)$, and blue otherwise.

By Ramsey’s Theorem for $r$-sets, there exists an infinite set $M_1$ that is monochromatic under this colouring.

• (1) Suppose $M_1$ is red. Then $c$ is constant on $M_1$.

  Let $i<j$, $k<l$. Pick $m<n$ (in $M_1$) bigger than all $4$. Then $i<j<m<n$ hence $c(ij)=c(mn)$. Also, $k<l<m<n$, so $c(kl)=c(mn)$. So $c$ is constant on $M_1$.

• (2) Now let’s assume $M_1$ is blue. So for $i<j<k<l$ we have $c(ij)\ne c(kl)$. Next: colour $M_1^{(4)}$ as follows: we will say that $\{i,j,k,l\}$ is green if $c(il)=c(jk)$, and purple otherwise. By Ramsey’s Theorem for $r$-sets we can pick infinite $M_2\subset M_1$ monochromatic.

  We claim that $M_2$ cannot be green. This is because if $M_2$ is green, let $i<j<k<l<m<n$ in $M_2$. Then:

  • $\{i<j<k<n\}$ gives us that $c(in)=c(jk)$

  • $\{i<l<m<n\}$ gives us that $c(in)=c(lm)$

  But using these we get $c(jk)=c(lm)$, which contradicts the fact that $\{i<j<k<l\}$ is blue.

  Therefore $M_2$ is purple: for $i<j<k<l$ we have $c(il)\ne c(jk)$.

  Next we colour $M_2^{(4)}$ as follows: $\{i<j<k<l\}$ is orange if $c(ik)=c(jl)$, and white otherwise. Again, by Ramsey’s Theorem for $r$-sets we can pick an infinite $M_3\subset M_2$ such that it is monochromatic with respect to this colouring.

  We claim that $M_3$ cannot be orange. If it is, then we again consider $i<j<k<l<m<n$:

  • $\{j<l<m<n\}$ gives that $c(jm)=c(ln)$

  • $\{i<j<k<m\}$ gives that $c(jm)=c(ik)$

  Hence $c(ik)=c(ln)$, which contradicts the fact that $\{i<j<l<n\}$ is blue.

  Therefore $M_3$ is white. This finally tells us (using earlier working) that given any pair disjoint edges, the colours must be different.

  Now, we colour $M_3^{(3)}$ via: $\{i<j<k\}$ yellow if $c(ik)=c(jk)$, and pink otherwise. By Ramsey’s Theorem for $r$-sets, there is an infinite $M_4\subset M_3$ that is monochromatic.

  We claim that $M_4$ is not yellow. If it is, then given $i<j<k<l$, we have $c(ij)=c(jk)=c(kl)$, which contradicts blueness.

  Thus for any $i<j<k$ in $M_4$, we have $c(ij)\ne c(jk)$.

  Finally: we colour $M_4^{(3)}$ with 4 colours, with $\{i<j<k\}$ coloured according to:

  • turquoise if $c(ij)=c(ik)$ and $c(ik)=c(jk)$

  • magenta if $c(ij)=c(ik)$ and $c(ik)\ne c(jk)$

  • cyan if $c(ij)\ne c(ik)$ and $c(ik)=c(jk)$

  • maroon if $c(ij)\ne c(ik)$ and $c(ik)\ne c(jk)$

  By Ramsey’s Theorem for $r$-sets, there exists a monochromatic set $M_5\subset M_4$. It cannot be turquoise because $c(ij)=c(jk)$ contradicts $M_4$. Then:

  • magenta implies case (iii)

  • cyan implies case (iv)

  • maroon implies (ii), i.e. injective. □

Proof. Exercise. Note that this proof is examinable (because the ideas are exactly the same as those in the previous theorem). □

Proof. Claim: For any $r\le k$ there exists an $n$ such that if $[n]$ is $k$-coloured then either:

• there exists a monochromatic arithmetic progression of length $3$

• there exists $r$ colour-focused arithmetic progressions of length $2$

The proof is by induction on $r$.

Base case $r=1$ we can take $n=k+1$, since 2 numbers will have the same colour.

Suppose the result is true for $r-1$ and let $n$ be an $n$ that satisfies the property in the claim.

We will show that $N=(k^{2n}+1)2n$ works for $r$. Let $c:[(k^{2n}+1)2n]\to [k]$ be a colouring. We will split the ground set into $k^{2n}+1$ blocks of length $2n$. Call the blocks $B_i$.

If there exists a monochromatic arithmetic progression of length $3$ in this colouring, then we are done. So assume not.

By the induction hypothesis, the first half of each $B_i$ has $r-1$ colour-focused arithmetic progressions of length $2$. Because $|B_i|=2n$, each block also contains their focus.

For a set $|M|=2n$, there are exactly $k^{2n}$ ways to $k$-colour it. So there exists two blocks $B_p$ and $B_{p+t}$ that are identically coloured.

Let $\{a_i,a_i+d_i\}$ be the $r-1$ colour-focused arithmetic progressions in $B_p$. Then $\{a_i+2nt,a_i+d_i+2nt\}$ are the corresponding ones in $B_{p+t}$. Let $f$ be the focus in $B_p$, so therefore $f+nt$ is the focus in $B_{p+t}$.

Now take $\{a_i,a_i+d_i+2nt\}$ for $i\in [r-1]$, and $\{f,f+2nt\}$. Since $a_i+2d_i=f$, we have $a_i+2d_i+4nt=f+4nt$. So all $r$ of these sequences are focused at $f+4nt$.

We know that $\{a_i,a_i+d_i+nt\}$ and $\{f,f+2nt\}$ are monochromatic by the choice of $B_p$, $B_{p+t}$. Why colour focused? $\{a_i,a_i+2nt\}$ have different colours by induction hypothesis. Also, because $c$ was assumed to have no monochromatic arithmetic progression of length $3$, the colours of $\{f,f+2nt\}$ must be different to all the colours of the above $r-1$ arithmetic progressions of length $2$. Thus we have $r$ colour-focused arithmetic progressions of length $2$ in $[(k^{2n}+1)2n]$. □

Proof. This will be by induction on $m$. For any $k$:

$m=1$ is trivial.

$m=2$ is pigeonhole.

$m=3$ is Theorem 1.7.

Assume that this is true for some $m-1$ fixed, but for any $k$. In other words, $W(k,m-1)$ exists for all $k\ge 1$.

Claim: For every $r\le k$ there exists $n$ such that we always have one of the following:

• have a monochromatic arithmetic progression of length $m$

• $r$ colour-focused arithmetic progressions of length $m-1$

When $r=k$ we are done by looking at the focus. Now we prove the claim. We will prove it by induction on $r$.

For $r=1$ we can take $n=W(k,m-1)$.

Now assume that the result is true for $r-1$ and that there does not exist a monochromatic arithmetic progression of length $m$. We will show that $n$ works for $r-1$, then $W(k^{2n},m-1)2n$ will work for $r$.

Aim: whenever we $k$-colour $[W(k^{2n},m-1)2n]$ we can find $r$ colour-focused arithmetic progressions of length $m-1$. Let $B_1=\{1,2,\dots ,2n\}$, $B_2=\{2n+1,\dots ,4n\}$ etc, i.e. $B_i=[2n(i-1)+1,2ni]$ for $i\in \{1,\dots ,W(k^{2n},m-1)\}$.

Let us look at the indices of these blocks. I colour $i$ with $k^{2n}$ colours like so:

We therefore colour $[W(k^{2n},m-1)]$ with $k^{2n}$ colours. By the definition of $W$, there exists a monochromatic arithmetic progression of length $m-1$ (with respect to $c^{\prime }$). Say $\alpha ,\alpha +t,\dots ,\alpha +(m-2)t$.

So the respective blocks $B_{\alpha },B_{\alpha +2t},\dots ,B_{\alpha +(m-2)t}$ are identically coloured. Look at $B_{\alpha }$. It has length $2n$, so by induction $B\alpha$ contains $r-1$ colour-focused arithmetic progressions of length $m-1$ together with their focus.

Let $A_i=\{a_i,a_i+di,\dots ,a_i+(m-2)di\}$ for $i\in \{1,\dots ,r-1\}$. Let $f$ be their focus. Look at $B_i=\{a_i,a_i+di+2nt,a_i+2di+4nt,\dots ,a_i+(m-2)di+2(m-2)t\}$, $i=1,\dots ,r-1$.

They are monochromatic because the blocks are identically coloured and the $B_i$s are monochromatic. Since the colour of $A_i$ is the colour of $B_i$ and the $A_i$s are colour-focused, we must have that the $B_i$s have pairwise distinct colours.

Remember that the $A_i$s are are focused at $f_i$ and the colour of $f_i$ is different than the colour of all the $A_i$s. Note $f_i=a_i+(m-1)di$.

Look at $A=\{f,f+2nt,2+4nt,\dots ,f+2n(m-2)t\}$. This is an arithmetic progression of length $m-1$ and monochromatic and of a different colour from all of the $A_i$s.

Enough to show $a_i+(m-1)(di+2nt)=f+2n(m-1)t$ for all $i$, which is equivalent to $a_i+(m-1)di=f$, which is true as all the $B_i$s are focused at $f$. □

Proof. By induction on the number of colours. $k=1$ is trivial.

Assume that the case for $k-1$ colours is true. So there exists $n$ that works for $m$ and $k-1$.

We will show that $W(k,n(m-1)+1)$ works for $m$ and $k$. If $[W(k,n(m-1)+1)$ are $k$-coloured, then there exists a monochromatic arithmetic progression (say red) of length $n(m-1)+1$, say $a,a+d,\dots ,a+dn(m-1)$.

If any of $d,2d,\dots ,nd$ is red, then we are done: e.g. $a,a+rd,\dots ,a+r(m-1)d$ for some $r\in [n]$.

If not, the set $\{d,2d,\dots ,nd\}$ is $k-1$-coloured.. This involves a $(k-1)$ colouring on $[n]$, therefore there exist $b,b+r,\dots ,b+(m-1)r$ and $r$ the same colour. This translates to $db,db+r,\dots ,db+d(m-1)r,dr$ monochromatic. □

Proof of The Hales-Jewett Theorem. The proof is by induction on the size of the alphabet, i.e. $m$.

$m=1$ is trivially true.

Assume $m\ge 1$ and assume $HJ(m-1,k)$ exists for all $k$.

Claim: for every $1\le r\le k$ there exists $n$such that in ${[m]}^n$

• (1) either there exists monochromatic combinatorial lines
• (2) there exists $r$ colour-focused combinatorial lines

Then we are done by $r=k$ and looking at the focus.

Now we prove the claim:

$r=1$: look in ${[m-1]}^{n^{\prime }}\subset {[m]}^n$ We can take $HJ(m-1,k)$.

Now assume $r>1$ and that $n$ is suitable for $r-1$. We will show that $n+HJ(m-1,k^{m^n})$ is suitable for $r$. Let $N=HJ(m-1,k^{m^n})$ for convenience.

Need: given $c$ a $k$-colouring of ${[m]}^{n+N}$ with no monochromatic combinatorial lines, we can find $r$ colour-focused combinatorial lines. Look at ${[m]}^{n+N}$ as ${[m]}^n\times {[m]}^N$, with ${[m]}^n=\{a_1,\dots ,a_{m^n}\}$.

Let us colour ${[m]}^N$ as follows:

By The Hales-Jewett Theorem there exists a combinatorial lines $L$ with active coordinates $I$ such that

But now this induces $c^{″}:{[m]}^n\to k$ where $c^{″}(a)=c(a,b)$ for any $b\in L\setminus \{L^{+}\}$. By the definition of $n$, there exist $r-1$ colour-focused combinatorial lines (for $c^{″}$) $L_1,L_2,\dots ,L_{r-1}$, focused at $f$, and with active coordinates $I_1,I_2,\dots ,I_{r-1}$.

Finally: look at the combinatorial lines that start at $L_i^{-}\times L^{-}$ and active coordinates $I_i\cup I$. These give $r-1$ combinatorial lines, and the combinatorial lines that starts at $f\times L^{-}$ with active coordinates $I$. All focused at $f\times L^{+}$. Then done. □