Difference between revisions of "Coloring.tex"

From Polymath1Wiki
Jump to: navigation, search
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 $2^{k/4}/3(k^{4})$ to roughly $2^{k/2-3}/k^{2}$ . The previous method the sum of the squares of the coordinates and looked for sequences free of quadratic progressions $\cite{beck}$.
+
$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)$. We can then use this lower bound for $HJ(k,2)$, $2^{k}/k^{2}$This improves on the previous method of computing the $M(k,r)$ It also improves the previous lower bound for $M(k,2)$ from $2^{k/4}/3(k^{4})$ to $2^{k/2-3}/(k/2)^{2}$ if k is even, $2^{k/2-3}/(k+1/2)^{2}$ if k is odd. The previous method the sum of the squares of the coordinates and looked for sequences free of quadratic progressions $\cite{beck}$.

Revision as of 07:55, 28 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)$. We can then use this lower bound for $HJ(k,2)$, $2^{k}/k^{2}$This improves on the previous method of computing the $M(k,r)$ It also improves the previous lower bound for $M(k,2)$ from $2^{k/4}/3(k^{4})$ to $2^{k/2-3}/(k/2)^{2}$ if k is even, $2^{k/2-3}/(k+1/2)^{2}$ if k is odd. The previous method the sum of the squares of the coordinates and looked for sequences free of quadratic progressions $\cite{beck}$.