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 we shall ensure that the colouring is insensitive to changes between k-1 and k. To emphasize how easy this is, I shall paste the above paragraphs into this section and make the necessary adjustments.

Let [math]\displaystyle{ t_1,t_2,\dots,t_m }[/math] be a rapidly increasing sequence of integers, to be chosen later (including m), let [math]\displaystyle{ n=t_1+\dots+t_m }[/math] and consider an r-colouring of [math]\displaystyle{ [k]^n=[k]^{t_1}\times\dots\times[k]^{t_m}. }[/math] Now define an induced [math]\displaystyle{ k^{n-t_m} }[/math]-colouring on [math]\displaystyle{ [k]^{t_m} }[/math] by colouring each x according to the function that takes [math]\displaystyle{ w\in[k]^{n-t_m} }[/math] to the colour of [math]\displaystyle{ (w,x). }[/math] By HJ(2) (a trivial application of the pigeonhole principle, as we saw above), we can find a monochromatic combinatorial line [math]\displaystyle{ L_r }[/math] in [math]\displaystyle{ [k]^{t_m} }[/math] such that the first two points in that line have the same (induced) colour. For this we need [math]\displaystyle{ t_r\geq HJ(2,k^{n-t_m})=k^{n-t_m}. }[/math]

Now pass to the subspace [math]\displaystyle{ [k]^{n-t_m}\times L_m, }[/math] and note that if you change the final coordinate of a sequence in this space from a 1 to a 2, or vice versa, then it does not change the colour of the sequence. Inside this subspace, run precisely the same argument, but this time with [math]\displaystyle{ [k]^{t_{m-1}} }[/math] taking over the role of [math]\displaystyle{ [k]^{t_m} }[/math] and [math]\displaystyle{ L_m }[/math] taking over the role of [math]\displaystyle{ [k]^{t_{m-1}}. }[/math]

After the second stage of the iteration, for which we require that [math]\displaystyle{ t_{m-1}\geq HJ(2,k^{n-t_r-t_{m-1}+1})=k^{n-t_m-t_{m-1}}+1, }[/math] we have a line [math]\displaystyle{ L_{m-1} }[/math] such that the colour of a point in [math]\displaystyle{ [k]^{t_1}\times\dots\times[k]^{t_{m-2}}\times L_{m-1}\times L_m }[/math] does not change if you change any of the coordinates in [math]\displaystyle{ L_{m-1}\times L_m, }[/math] from a 1 to a 2 or vice versa.

Continuing this process, one ends up with a subspace [math]\displaystyle{ L_1\times\dots\times L_m }[/math] such that the colour of a point does not change if you change a coordinate from a 1 to a 2 or vice versa. This reduces the problem to HJ(k-1), so we can take m to be HJ(k-1,r) and we are done. To spell it out, consider the set of all points in [math]\displaystyle{ L_1\times\dots\times L_m }[/math] that have no variable coordinate equal to 1. Inside this set, we can find, by HJ(k-1,m), a combinatorial line such that all points in the line with variable coordinate not equal to 1 have the same colour. But by the way the subspace is chosen, we still have the same colour if we change the variable coordinate to a 1.