Coloring.tex: Difference between revisions
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
By iterating the Hales-Jewett theorem, one can also show that one of the colour classes contains an $m$-dimensional combinatorial subspace, if $n$ is sufficiently large depending on $k$, $r$ and $m$. | By iterating the Hales-Jewett theorem, one can also show that one of the colour 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)$. | 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)$. This method is not new but the lower bounds appear to be new \cite{beck},\cite{shelah}. | ||
\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} | ||
| Line 34: | Line 34: | ||
A related problem is if we colour the elements of $k^{n}$ with $r$ colours and look for a geometric line. Call the numbers associated with this problem $n = M(k,r)$. We have a relationship between the $HJ(k,r)$ and the $M(k,r)$. We can start with a colouring of $[k]{}^n$ free of combinatorial lines and get a colourings of $[k]{}^2n-1$ and $k^{2n-1}$ free of geometric lines. | A related problem is if we colour the elements of $k^{n}$ with $r$ colours and look for a geometric line. Call the numbers associated with this problem $n = M(k,r)$. We have a relationship between the $HJ(k,r)$ and the $M(k,r)$. We can start with a colouring of $[k]{}^n$ free of combinatorial lines and get a colourings of $[k]{}^2n-1$ and $k^{2n-1}$ free of geometric lines. | ||
We send each point of the original space to sets of points in the second space. When we go from | We send each point of the original space to sets of points in the second space. When we go from | ||
$k^{n}$ to $k^{2n-1}$ we send coordinates equal to $n$ to $n$ and for the rest let the coordinate be equal to $i$, then we send it either to $2n-i$ or $i$. So in this mapping a point can have one to $2^{k}$ colourings. When we go from $k^{n}$ to $k^{2n}$ let the coordinate be equal to $i$, then we send it either to $2n-i$ or $i$. So in this mapping each point has $2^{k}$ colourings. In both of these colourings the preimage of a geometric line is a combinatorial line. So a combinatorial line free colouring becomes a geometric line free coloring and we get $M(2k-1,r)$ and $M(2k,r)$ are both greater than or equal to $HJ(k,r)$. This improves on the previous method of computing the $M(k,r)$ It also improves the previous lower bound for $M(k,2)$ from roughly $2^{k/4}$ to roughly $2^{k/4}$. | $k^{n}$ to $k^{2n-1}$ we send coordinates equal to $n$ to $n$ and for the rest let the coordinate be equal to $i$, then we send it either to $2n-i$ or $i$. So in this mapping a point can have one to $2^{k}$ colourings. When we go from $k^{n}$ to $k^{2n}$ let the coordinate be equal to $i$, then we send it either to $2n-i$ or $i$. So in this mapping each point has $2^{k}$ colourings. In both of these colourings the preimage of a geometric line is a combinatorial line. So a combinatorial line free colouring becomes a geometric line free coloring and we get $M(2k-1,r)$ and $M(2k,r)$ are both greater than or equal to $HJ(k,r)$. This improves on the previous method of computing the $M(k,r)$ It also improves the previous lower bound for $M(k,2)$ from roughly $2^{k/4}$ to roughly $2^{k/4}$ $\cite{beck}$. | ||
Revision as of 12:36, 26 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 colour 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)$. This method is not new but the lower bounds appear to be new \cite{beck},\cite{shelah}.
\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}
A related problem is if we colour the elements of $k^{n}$ with $r$ colours and look for a geometric line. Call the numbers associated with this problem $n = M(k,r)$. We have a relationship between the $HJ(k,r)$ and the $M(k,r)$. We can start with a colouring of $[k]{}^n$ free of combinatorial lines and get a colourings of $[k]{}^2n-1$ and $k^{2n-1}$ free of geometric lines. We send each point of the original space to sets of points in the second space. When we go from $k^{n}$ to $k^{2n-1}$ we send coordinates equal to $n$ to $n$ and for the rest let the coordinate be equal to $i$, then we send it either to $2n-i$ or $i$. So in this mapping a point can have one to $2^{k}$ colourings. When we go from $k^{n}$ to $k^{2n}$ let the coordinate be equal to $i$, then we send it either to $2n-i$ or $i$. So in this mapping each point has $2^{k}$ colourings. In both of these colourings the preimage of a geometric line is a combinatorial line. So a combinatorial line free colouring becomes a geometric line free coloring and we get $M(2k-1,r)$ and $M(2k,r)$ are both greater than or equal to $HJ(k,r)$. This improves on the previous method of computing the $M(k,r)$ It also improves the previous lower bound for $M(k,2)$ from roughly $2^{k/4}$ to roughly $2^{k/4}$ $\cite{beck}$.
