Proof of Hales–Jewett number

Question

In the Wikipedia page: https://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem, and the Polymath site http://michaelnielsen.org/polymath1/index.php?title=Coloring_Hales-Jewett_theorem, it says that the Hales–Jewett number $H(3, 2)=4$. However, I am unable to construct a $3 \times 3 \times 3$ cube with two colours which avoids a combinatorial line of the same colour. If the Polymath site is correct, then there is such a colouring.

So my question is: Is there a colouring, and if so, what is it?

Answer 1

Here is a valid coloring of the $3 \times 3 \times 3$ cube.

The $(1,1,1)$ cell is the bottom left cell of the leftmost square.

Note the antidiagonal line in the third square with all three cells colored red. (And another antidiagonal line in the first square with all three cells colored blue. There might be more.) This is okay, because it's not a combinatorial line: one coordinate is increasing while another is decreasing.

If you consider the geometric variant of Hales-Jewett, and forbid any three collinear cells from having the same color, then my SAT solver tells me that there is no valid coloring.

---

Edit: A less ad-hoc way of coloring the cube than the above (which was found by a SAT solver) is to use the lower bound from van der Waerden's theorem. We can color the set $\{1, 2, \dots, 7\}$ red and blue while avoiding monochromatic arithmetic progressions of length $3$: color $\{1,3,6\}$ red and $\{2,4,5,7\}$ blue. Then color the $3 \times 3 \times 3$ cube by giving $(x,y,z)$ the color of $x+y+z-2$. This produces the following coloring (with "layers" of $x+y+z=c$ indicated by shading):

So now it's straightforward to check that this coloring works. We can extend the coloring of $\{1, 2, \dots, 7\}$ to $\{1, 2, \dots, 8\}$ by coloring $8$ red, but to color the $3 \times 3 \times 3 \times 3$ cube, we would need a coloring of $\{1, 2, \dots, 9\}$, which (unsurprisingly) doesn't exist.

Answer 2

Here is a $2-$coloring of a $3×3×3$ cube which avoids a combinatorial line of the same colour.

The bottom layer is colored as:

\begin{array}{|c|c|} \hline 0& 1 & 0 \\ \hline 0& 0& 1 \\ \hline 1& 0& 1\\ \hline \end{array}

The middle layer is colored as:

\begin{array}{|c|c|} \hline 0& 0 & 1 \\ \hline 1& 1& 0\\ \hline 0& 1& 0\\ \hline \end{array}

The top layer is colored as:

\begin{array}{|c|c|} \hline 1& 1 & 0 \\ \hline 0& 0& 1 \\ \hline 1& 0& 0 \\ \hline \end{array}

We can easily check manually that the $4$ body diagonals are not monochromatic as well. Hence, this is the desired coloring!