The Hales-Jewett Theorem

(The Hales-Jewett theorem)

Settings: Let \(m,k\in \mathbb{N}\text{.}\) As an alphabet on \(m\) symbols we take \(A=[1,m]\text{.}\) Reminder: A root \(\tau \in [1,m]_\ast^n\) is an \(n\)-word on \(m+1\) symbols, \(1,2,\ldots, m\) and \(\ast\text{,}\) that contains the symbol \(\ast\text{.}\) A combinatorial line in \([1,m]^n\) rooted in \(\tau\) is the set of words

\begin{equation*} L_\tau=\{ \tau _a:a\in [1,m]\}\text{.} \end{equation*}

Here, for \(a\in [1,m]\) and \(i\in [1,n]\text{,}\)

\begin{equation*} \tau_a(i)= \left\{ \begin{array}{rcl} \tau(i)\amp \mbox{ if } \amp \tau(i)\not= \ast ,\\ a\amp \mbox{ if } \amp \tau(i)= \ast . \end{array} \right. \end{equation*}

Focussed and Colour-Focussed Lines:
- Let \(r\in \mathbb{N}\) and let and \(\tau^{(1)}, \tau^{(2)},\ldots, \tau^{(r)}\in [1,m]_\ast^n\) be \(r\) roots. We say that the corresponding combinatorial lines are focussed at \(f\in [1,m]^n\) if
  
  \begin{equation*} \tau^{(1)}_m= \tau^{(2)}_m=\cdots=\tau^{(r)}_m=f\text{.} \end{equation*}
  
  Example:
  
  Consider \(\tau^{(1)}, \tau^{(2)},\tau^{(3)}\in [1,4]_\ast^4\) given by
  
  \begin{equation*} \tau^{(1)}=\ast \ \ast \ 3 \ \ast, \ \tau^{(2)}= \ast \ 4 \ 3 \ \ast, \ \tau^{(3)}=\ast \ 4 \ 3 \ 4\text{.} \end{equation*}
  
  Then
  
  \begin{equation*} \tau^{(1)}_4=\Box \ \Box \ 3 \ \Box, \ \tau^{(2)}_4= \Box \ 4 \ 3 \ \Box, \ \tau^{(3)}_4=\Box \ 4 \ 3 \ 4\text{.} \end{equation*}
  
  See Figures 5.1.14 and Figure 5.2.5.
  
  Hence the corresponding combinatorial lines are focussed at \(f=4 \ 4 \ 3\ 4\text{:}\)
  
  \begin{equation*} \begin{array}{|c|c|c|} \hline L_{\tau^{(1)}}\amp L_{\tau^{(2)}}\amp L_{\tau^{(3)}}\\ \hline \color{red}{1}\ \color{red}{1}\ 3\ \color{red}{1}\amp \color{red}{1} \ 4\ 3\ \color{red}{1}\amp \color{red}{1} \ 4\ 3\ 4\\ \color{red}{2}\ \color{red}{2}\ 3\ \color{red}{2}\amp \color{red}{2} \ 4\ 3\ \color{red}{2}\amp \color{red}{2} \ 4\ 3\ 4\\ \color{red}{3}\ \color{red}{3}\ 3\ \color{red}{3}\amp \color{red}{3} \ 4\ 3\ \color{red}{3}\amp \color{red}{3} \ 4\ 3\ 4\\ \color{red}{4}\ \color{red}{4}\ 3\ \color{red}{4}\amp \color{red}{4} \ 4\ 3\ \color{red}{4}\amp \color{red}{4} \ 4\ 3\ 4\\ \hline \end{array} \end{equation*}
  
  Figure 5.2.4. Three focussed lines in \([1,4]^4\text{.}\)
  
  Figure 5.2.5. Three lines in \([1,4]^4\) focussed at \(f\text{.}\)
- Let \(c\) be a \(k\)-colouring of \([1,m]^n\) and let and \(\tau^{(1)}, \tau^{(2)},\ldots, \tau^{(r)}\in [1,m]_\ast^n\) be \(r\) roots. See Figures 5.2.6.
  
  Figure 5.2.6. \(r\) colour-focussed lines: different colours and \(\tau^{(1)}_m= \tau^{(2)}_m=\cdots= \tau^{(r)}_m\text{.}\)
Strategy. Induction on \(m\text{.}\)

Reminder: The Hales-Jewett Theorem. Let \(m,k\in \mathbb{N}\) and let \(A\) be an alphabet on \(m\) symbols. There exists an \(n\in \mathbb{N}\) such that whenever \(A^n\) is \(k\)-coloured there exists a monochromatic line.

Base Case. If \(m=1\) then \(H(1,k)=1\) for any number of colours \(k\text{.}\) Inductive step. Given \(m>1\text{,}\) we assume that \(HJ(m-1,k)\) exists for all \(k\text{.}\)
1. Claim. For all \(1\leq r\leq k\text{,}\) there exists \(n\) such that whenever \([1,m]^n\) is \(k\) coloured, there exists either a monochromatic line or \(r\) colour-focussed lines.
2. Base Case. Let \(k\in \mathbb{N}\) and let \(r=1\text{.}\) We take \(n=HJ(m-1,k)\text{.}\)
  
  Let \(c\) be a \(k\)-colouring of \([1,m]^n\text{.}\) See Figure 5.2.7.
  
  Figure 5.2.7. The colouring \(c\) of \([1,m]^n\) induces a \(k\)-colouring of \([1,m-1]^n\text{.}\) Our choice of \(n\) guarantees the existence of a monochromatic line in \([1,m-1]^n\text{.}\)
  
  Figure 5.2.8. Where are you?
3. Inductive Step. Let \(r\in[1,k-1]\) and let \(n=n(r)\) be such that whenever \([1,m]^n\) is \(k\) coloured, there exists either a monochromatic line or \(r\) colour-focussed lines. Let \(n'=HJ(m-1,k^{m^n})\) and let \(N=n+n'\text{.}\) Let \(c\) be a \(k\)-colouring of \([1,m]^N=[1,m]^{n+n'}\) without a monochromatic line. See Figure 5.2.9.
  
  Figure 5.2.9. The \(k\)-colouring \(c\) of \([1,m]^N=[1,m]^{n+n'}\) without a monochromatic line.
  1. A \(c\) induced \(k^{m^n}\)-colouring of \([1,m-1]^{n'}\text{:}\) Step 1. See Figure 5.2.10.
    
    Figure 5.2.10. Choose \(b=b_1b_2\cdots b_{n'}\in[1,m-1]^{n'}\text{.}\) Consider \(c_b\text{,}\) a \(k\)-colouring of \([1,m]^n\) such that for \(a\in[1,m]^n\text{,}\) \(c_b(a)=c(ab)\text{.}\)
    
    Step 2. Note that there are \(k^{m^n}\) \(k\)-colourings of \([1,m]^n\text{.}\) See Figur 5.2.11.
    
    Figure 5.2.11. The mapping \(\chi: b\mapsto c_b\) is a \(k^{m^n}\)-colouring of \([1,m-1]^{n'}\text{.}\)
    
    Step 3. There is a \(\chi\)-monochromatic line in \([1,m-1]^{n'}\text{.}\) See Figure 5.2.12.
    
    Figure 5.2.12. There is a \(\chi\)-monochromatic line \(L_\tau\) in \([1,m-1]^{n'}\text{.}\)
  2. Reminder - Inductive Step. Let \(r\in[1,k-1]\) and let \(n=n(r)\) be such that whenever \([1,m]^n\) is \(k\)–coloured, there exists either a monochromatic line or \(r\) colour-focussed lines. Let \(n'=HJ(m-1,k^{m^n})\) and let \(N=n+n'\text{.}\) Let \(c\) be a \(k\)-colouring of \([1,m]^N=[1,m]^{n+n'}\) without a monochromatic line. See Figure 5.2.13.
    
    Figure 5.2.13. The \(k\)-colouring \(c\) of \([1,m]^N=[1,m]^{n+n'}\) without a monochromatic line.
  3. A \(c\) induced \(k\)-colouring of \([1,m]^{n}\text{:}\) Step 1 There is a \(\chi\)-monochromatic line in \([1,m-1]^{n'}\text{.}\) See Figure 5.2.14.
    
    Figure 5.2.14. \(L_\tau\) is monochromatic: \(c_{\tau_1}=c_{\tau_2}=\cdots=c_{\tau_{m-1}}\text{.}\)
    
    Step 2. A \(k\)-colouring \(c_\tau\) of \([1,m]^{n}\) emerges. See Figure 5.2.15.
    
    Figure 5.2.15. The \(k\)-colouring \(c_\tau\) of \([1,m]^{n}\) is with the property that, for any \(a\in[1,m]^n\) and any \(i\in[1,m-1]\text{,}\) \(c_\tau(a)=c(a\tau_i)\text{.}\)
    
    Step 3. Back to colour-focussed lines. See Figure 5.2.16.
    
    Figure 5.2.16. There are \(r\) \(c_\tau\)-coloured-focussed lines \(L_{\sigma^{(1)}}\text{,}\)…, \(L_{\sigma^{(r)}}\) in \([1,m]^{n}\) with the focus \(f\) and one \(\chi\)-monochromatic line \(L_\tau\) in \([1,m]^{n'}\) with the focus \(\tau_{m}\text{.}\) None of the lines \(L_{\sigma^{(1)}}\text{,}\) …, \(L_{\sigma^{(r)}}\) is monochromatic.
  4. Making new roots from old: We define \(r+1\) roots in \([1,m]_\ast^N\) as follows (see Figure 5.2.17):
    
    \begin{equation*} \tau^{(1)}=\sigma^{(1)}\tau, \ \tau^{(2)}=\sigma^{(2)}\tau, \ldots, \tau^{(r)}=\sigma^{(r)}\tau, \ \tau^{(r+1)}=f\tau\text{.} \end{equation*}
    
    Figure 5.2.17. There are \(r+1\) \(c\)-coloured-focussed lines \(L_{\tau^{(1)}}\text{,}\) …, \(L_{\tau^{(r+1)}}\) in \([1,m]^{N}\) with the focus \(f\tau_m\text{.}\)
  5. Where Are You?
    
    Figure 5.2.18. Where are you?
  6. Let \(r=k\text{.}\) See Figure 5.2.19.
    
    Figure 5.2.19. What is the colour of the focus \(f\text{?}\) There is a monochromatic line!
  7. Done!
    
    \begin{equation*} HJ(m-1,k) \mbox{ exists } \Rightarrow HJ(m,k) \mbox{ exists } \end{equation*}

Introduction to Ramsey Theory: Lecture notes for undergraduate course

Section 5.2 The Hales-Jewett Theorem

Theorem 5.2.1.

Definition 5.2.2.

Proof.