Hales-Jewett Number $HJ(2,r)$

189 Views Asked by At

I'm trying to find the exact value for the Hales-Jewett number $HJ(2,r)$, where $HJ(k,r)$ is defined as the smallest $n$ so that any coloring of the elements of $[k]^n$ by $r$ colors has a monochromatic combinatorial line.

It seems like a simple (maybe even trivial) problem, but I'm not sure how to proceed since I'm still trying to wrap my head around combinatorial lines.

1

There are 1 best solutions below

0
On BEST ANSWER

Consider the points in $[2]^r$ of the form:

$(1,1,1,\ldots, 1),$

$(2,1,1,\ldots, 1)$,

$(2,2,1,\ldots, 1),$

$\qquad\ddots$

$(2,2,2,\ldots, 2)$.

Any pair of these form a combinatorial line. As there $r+1$ of these points, in any $r$-colouring, some pair must have the same colour.

Conversely, if $k<r$, then we may $r$-colour $[2]^k$ by number of co-ordinates equal to $2$. Then any monochromatic pair of points will not form a combinatorial line, as moving from one point to the other, there will exist a co-ordinate where a $1$ changes to a $2$, as well as a co-ordinate where a $2$ changes to a $1$.

Thus we have $HJ(2,r)=r$.