Coloring Hales-Jewett theorem

Coloring Hales-Jewett theorem (k=3): If n is sufficiently large depending on c, and [math]\displaystyle{ [3]^n }[/math] is partitioned into c color classes, then one of the color classes contains a combinatorial line.

This is a consequence of the Density Hales-Jewett theorem, and also of the Graham-Rothschild theorem.

Iterating the Hales-Jewett theorem, we also see that one of the color classes contains an m-dimensional combinatorial subspace, if n is sufficiently large depending on c and m.

There are two combinatorial proofs of this theorem: the original one by Hales and Jewett, and a second proof by Shelah.

There is an infinitary generalisation of this theorem known as the Carlson-Simpson theorem.

Here is the Wikipedia entry on this theorem.

For a fixed c, the least n needed for the Hales-Jewett theorem to apply is denoted HJ(3,c). The following bounds are known:

[math]\displaystyle{ HJ(3,1) = 1 }[/math]

[math]\displaystyle{ HJ(3,2) = 4 }[/math]

[math]\displaystyle{ HJ(3,3) \gt 6 }[/math]

The original proof of the Hales-Jewett theorem

The first proof of the Hales-Jewett theorem was an abstraction of the argument used to prove van der Waerden's theorem. It goes like this. Let us write HJ(k,r) for the smallest n such that for every r-colouring of [math]\displaystyle{ [k]^n }[/math] there is a monochromatic combinatorial line. We shall attempt to bound HJ(k,r) in terms of the function [math]\displaystyle{ s\mapsto HJ(k-1,s), }[/math] which we may assume by induction to take finite values for every s.

Let [math]\displaystyle{ t_1,t_2,\dots,t_r }[/math] be a rapidly increasing sequence of integers, to be chosen later, let [math]\displaystyle{ n=t_1+\dots+t_r }[/math] and consider an r-colouring of [math]\displaystyle{ [k]^n=[k]^{t_1}\times\dots\times[k]^{t_r}. }[/math] Now define an induced [math]\displaystyle{ k^{n-t_r} }[/math]-colouring on [math]\displaystyle{ [k]^{t_r} }[/math] by colouring each x according to the function that takes [math]\displaystyle{ w\in[k]^{n-t_r} }[/math] to the colour of [math]\displaystyle{ (w,x). }[/math] By induction, we can find a monochromatic combinatorial line [math]\displaystyle{ L_r }[/math] in [math]\displaystyle{ [k]^{t_r} }[/math] such that all the points in that line have the same (induced) colour, with the possible exception of the point where the value of the variable coordinates is k. For this we need [math]\displaystyle{ t_r\geq HJ(k-1,k^{n-t_r}). }[/math]

Now pass to the subspace [math]\displaystyle{ [k]^{n-t_r}\times L_r, }[/math] and note that the only way a sequence in this space can depend on its final coordinate is through whether that final coordinate takes the value k or not. Inside this subspace, run precisely the same argument, but this time with [math]\displaystyle{ [k]^{t_{r-1}} }[/math] taking over the role of [math]\displaystyle{ [k]^{t_r}. }[/math] There is a choice here about what "precisely the same argument" means. It can either mean that we treat [math]\displaystyle{ [k]^{n-t_r}\times L_r }[/math] as [math]\displaystyle{ ([k]^{n-t_r-t_{r-1}}\times L_r)\times[k]^{t_{r-1}} }[/math] and talk about the original colouring, or it can mean that we restrict attention to the set [math]\displaystyle{ [k]^{n-t_r}=[k]^{t_1}\times\dots\times[k]^{t_{r-1}} }[/math] and talk about the colouring where the colour of w is the colour of (w,x) for the points [math]\displaystyle{ x\in L_r }[/math] with variable coordinate not equal to k. The usual argument goes via the second option, but for the sake of comparison with Shelah's proof it is nicer to go for the first (so what we are presenting here is not quite identical to the proof of Hales and Jewett).

After the second stage of the iteration, for which we require that [math]\displaystyle{ t_{r-1}\geq HJ(k-1,k^{n-t_r-t_{r-1}+1}), }[/math] we have a line [math]\displaystyle{ L_{r-1} }[/math] such that the colour of a point in [math]\displaystyle{ [k]^{t_1}\times\dots\times[k]^{t_{r-2}}\times L_{r-1}\times L_r }[/math] does not depend on which point you choose in [math]\displaystyle{ L_{r-1}\times L_r, }[/math] except if you change a non-k to a k or a k to a non-k.

Continuing this process, one ends up with a subspace [math]\displaystyle{ L_1\times\dots\times L_r }[/math] such that the colour of a point depends only on which of its coordinates are equal to k. This reduces the problem to HJ(2,r), which follows trivially from the pigeonhole principle. To spell it out, consider the points [math]\displaystyle{ (k-1,k-1,\dots,k-1), }[/math] [math]\displaystyle{ (k,k-1,k-1,\dots,k-1), }[/math] [math]\displaystyle{ (k,k,k-1,\dots,k-1),\dots(k,k,k,\dots,k). }[/math] There are r+1 of these points, so two of them have the same colour. Those two are the top two points of a combinatorial line, all the rest of which must have the same colour as well.

Shelah's proof of the Hales-Jewett theorem

This is very unfair to Shelah, but I am trying to present what he did as an almost trivial exercise in "turning an induction upside-down". The above proof used HJ(k-1) to create a subspace that we can treat as [math]\displaystyle{ [2]^r, }[/math] because the colouring in that subspace depends only on which coordinates are k and which are not k. Now let us try to use HJ(2) to create a subspace that we can treat as [math]\displaystyle{ [k-1]^m, }[/math] for some appropriate m, since in the subspace the colouring is insensitive to changes between k-1 and k.

To be continued.

[math]\displaystyle{  }[/math][math]\displaystyle{  }[/math][math]\displaystyle{  }[/math][math]\displaystyle{  }[/math][math]\displaystyle{  }[/math][math]\displaystyle{  }[/math][math]\displaystyle{  }[/math][math]\displaystyle{  }[/math]