Coloring.tex: Difference between revisions
No edit summary |
No edit summary |
||
| (8 intermediate revisions by 3 users not shown) | |||
| 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. | ||
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{}]. | 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 | 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{}], 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 $ | 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} | ||
\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} | ||
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}$ 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}$ images. 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}$ $\cite{beck}$. 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}$. | |||
Latest revision as of 08:08, 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}$ 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}$ images. 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}$ $\cite{beck}$. 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}$.
