Coloring.tex

\section{The coloring Hales-Jewett problem}\label{coloring-sec}

The Hales-Jewett theorem states that for every $k$ and every $r$ there exists an $n = HJ(k,r)$ such that if you colour the elements of $[k]{}^n$ with $r$ colours, then there must be a combinatorial line with all its points of the same colour.

This is a consequence of the Density Hales-Jewett theorem, since there must be a set of density at least $r^{-1}$ of elements of $[k]{}^n$ all of whose elements have the same colour. It also follows from the Graham-Rothschild theorem [\cite{}]. By iterating the Hales-Jewett theorem, one can also show that one of the color classes contains an $m$-dimensional combinatorial subspace, if $n$ is sufficiently large depending on $k$, $r$ and $m$.

A related idea is that of the Van der Waerden number $W(k,r)$ [\cite{waerden}], which is the length of the longest sequence $1,2,\ldots,n$ which can be $r$-coloured without a monochromatic arithmetic progression of length $k$. These numbers were used in this project to construct $r$-colourings of $[k]{}^m$ without combinatorial lines, and so provide new lower bounds for $HJ(k,r)$.

\begin{lemma} $HJ(k,r) \ge \lfloor (W(k,r)-1)/(k-1)\rfloor$ \end{lemma}

\begin{proof} Let $m = \lfloor (W(k,r)-1)/(k-1) \rfloor$. Suppose we have a Van der Warden colouring of $1, 2, \ldots W(k,r)$. Give each point $(a_1,a_2,\ldots,a_m) \in [k]{}^m$ the colour that corresponds to $1+\sum (a_j-1)$. The points of a combinatorial line give sums that form an arithmetic progression, and will therefore not be monochromatic. \end{proof}

A recent table of lower bounds for the Van der Waerden numbers can be found at \cite{heule}

These numbers were used to produce the following table of lower bounds for colouring Hales-Jewett numbers.

\begin{figure}[tb] \centerline{\begin{tabular}{l|lllll} $k\backslash r$ & 2 & 3 & 4 & 5 & 6 \\ \hline 3 & & 13 & 37 & 84 & 103 \\ 4 & 11 & 97 & 349 & 751 & 3259 \\ 5 & 59 & 302 & 2609 & 6011 & 14173 \\ 6 & 226 & 1777 & 18061 & 49391 & 120097 \\ 7 & 617 & 7309 & 64661 & & \\ 8 & 1069 & 34057 & & & \\ 9 & 3389 & & & & \end{tabular}} \caption{Lower bounds for colouring Hales-Jewett numbers} \label{HJcolour}\end{figure}