Set-polynomials and polynomial extension of the Hales-Jewett Theorem


An abstract, Hales-Jewett type extension of the polynomial van den Waerden Theorem [BL] is established:

THEOREM. Let $r,d, q \in \mathbb{N}$. There exists $N \in \mathbb{N}$ such that for any $r$-coloring of the set of subsets of $V = \{1,\ldots , N\}^d \times \{1,…, q\}$ there exist a set $a \subset V$ and a nonempty set $\gamma \subseteq \{1,…, N\}$ such that $a\cap (\gamma^d \times \{1,…,q\}) = \emptyset$, and the subsets $a, a \cup (y^d \times \{1\})$, $a \cup (\gamma^d \times \{2\}),…,$ $a \cup (\gamma^d \times \{q\})$ are all of the same color.

This “polynomial” Hales-Jewett theorem contains refinements of many combinatorial facts as special cases. The proof is achieved by introducing and developing the apparatus of set-polynomials (polynomials whose coefficients are finite sets) and applying the methods of topological dynamics.


Vitaly Bergelson

Alexander Leibman