Coloring.tex: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
\section{The coloring Hales-Jewett problem}\label{coloring-sec} | \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. | 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. | ||
| Line 8: | Line 9: | ||
\begin{lemma} $HJ(k,r) \ge \lfloor (W(k,r)-1)/(k-1)\rfloor$ \end{lemma} | \begin{lemma} $HJ(k,r) \ge \lfloor (W(k,r)-1)/(k-1)\rfloor$ \end{lemma} | ||
\begin{proof} | \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. | 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} | \end{proof} | ||
A recent table of lower bounds for the Van der Waerden numbers | 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. | These numbers were used to produce the following table of lower bounds for colouring Hales-Jewett numbers. | ||
\begin{figure}[tb] \centerline{\begin{tabular} | \begin{figure}[tb] \centerline{\begin{tabular}{l|lllll} | ||
k\r & 2 & 3 & 4 & 5 & 6 \\ | $k\backslash r$ & 2 & 3 & 4 & 5 & 6 \\ | ||
\hline | \hline | ||
3 & & 13 & 37 & 84 & 103 \\ | 3 & & 13 & 37 & 84 & 103 \\ | ||
| Line 25: | Line 28: | ||
8 & 1069 & 34057 & & & \\ | 8 & 1069 & 34057 & & & \\ | ||
9 & 3389 & & & & | 9 & 3389 & & & & | ||
\end{tabular}}\caption{Lower bounds for colouring Hales-Jewett numbers | \end{tabular}} | ||
\caption{Lower bounds for colouring Hales-Jewett numbers} | |||
\label{HJcolour}\end{figure} | \label{HJcolour}\end{figure} | ||
Revision as of 15:12, 25 July 2009
\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}
