Density versions of coloring theorems

Notation: $[k]=\{1,2,\ldots,k\}$;      $[k]^n=\{(x_1,\ldots,x_n) : x_i\in[k]\}$.

Definition 5.1   A subset $L\subseteq [k]^n$ with $k$ elements is called a combinatorial line if we can arrange the elements in an order so that in every coordinate either all the entries are the same or they form the sequence $1,2\ldots,k$, in that order.

Note: A combinatorial line is a ``SET" in the game ``SET." The converse is not true. (why?)

Theorem 5.2 (Hales-Jewett, 1963)   For all $k,\ell$ there exists an $n_0$ such that for all $n\geq n_0$ and any $k$-coloring of $[\ell]^n$, there exists a combinatorial line in one color.

Note: This theorem implies Van der Waerden's theorem:

Theorem 5.3 (Van der Waerden, 1927)   For any $k,\ell$ there exists $N_0$ such that for all $N\geq N_0$, if we color $[N]$ with $k$ colors, then there is an $\ell$-term arithmetic progression in one color.

The idea is to let $N_0=\ell^{n_0}$, and to associate with every number in $[N]$ the digits in its expansion in the base-$\ell$ number system. Then any combinatorial line would correspond to an arithmetic progression. (But not conversely. Why?)

Recall Szemerédi's Theorem, which is the ``density version'' of van der Waerden's Theorem:

Theorem 5.4 (Szemerédi, 1975)   For all $\epsilon > 0$ and $\ell$ there exists $N_0$ such that for all $N\ge N_0$, if $A\subseteq \{1,\dots,N\}$ and $\vert A\vert\geq \epsilon N$ then $A$ contains an $\ell$-term arithmetic progression.

The density version of the Hales-Jewett Theorem is:

Theorem 5.5 (Furstenberg-Katznelson)   For all $\epsilon > 0$ and all $\ell$ there exists $n_0$ such that for all $n\ge n_0$, if $A\subseteq [\ell]^n$ and $\vert A\vert\geq\epsilon\ell^n$, then $A$ contains a combinatorial line.