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]