Hales-Jewett theorem

Jewett–Hales theorem

One of the fundamental results in Ramsey theory.

Let $A = \{ a _ { 1 } , \dots , a _ { q } \}$ be a finite alphabet and let $A ^ { n }$ denote the set of $n$-tuples with entries from $A$. A set $\{ w ^ { 1 } , \dots , w ^ { q } \} \subset A ^ { n }$ consisting of $q$ $n$-tuples $w ^ { l } = ( w _ { 1 } ^ { l } , \dots , w _ { n } ^ { l } )$, $l = 1 , \dots , q$, is a combinatorial line if there exists a non-empty subset $I \subset \{ 1 , \dots , n \}$ such that for $i \in I$ and $l = 1 , \dots , q$ one has $w _ { i } ^ { l } = a _ { l }$ and for $i \in \{ 1 , \dots , n \} \backslash I$ one has $w _ { i } ^ { 1 } = \ldots = w _ { i } ^ { q }$. An alternative way of describing a combinatorial line is the following. Let $t \notin A$ be a "variable" . A variable word $w ( t )$ is a word over the alphabet $A \cup \{ t \}$ in which $t$ occurs. For $a \in A$, denote by $w( a )$ the word which results from replacing each occurrence of $t$ in $w ( t )$ by $a$. Then the set $\{ w ( a ) \} _ { a \in A }$ is a combinatorial line. For example, if $A = \{ 0,1,2,3,4 \}$ and $w ( t ) = 2 t 1 r 213$ then $\{2t1t213\}_{t \in A} = \{ 2010213,2111213,2212213,2313213, 2414213\}$ is a combinatorial line in $A ^ { 7 }$.

The Hales–Jewett theorem, proved in [a1], states that for any $q , r \in \mathbf{N}$ there exists an $N = N ( q , r ) \in \mathbf N$ such that if $A ^ { N }$ is partitioned into $r$ classes, then at least one of these classes contains a combinatorial line.

The following is an equivalent formulation of the Hales–Jewett theorem. Given a set $S$, let $\mathcal{F} ( S )$ denote the set of all finite subsets of $S$. For any $q , r \in \mathbf{N}$ there exists an $N = N ( q , r )$ so that if $S$ is a set with $ \geq N$ elements, then for any $r$-colouring of $\mathcal{F} ( S ) ^ { q }$ there exist a non-empty set $\gamma \in {\cal F} ( S )$ and sets $\alpha _ { 1} , \dots , \alpha _ { q } \in \mathcal{F} ( S )$ such that $\gamma \cap \alpha _ { 1 } = \ldots = \gamma \cap \alpha _ { q } = \emptyset$ and such that $( \alpha _ { 1 } , \dots , \alpha _ { q } )$, $( \alpha _ { 1 } \cup \gamma , \alpha _ { 2 } , \dots , \alpha _ { q } )$, $( \alpha _ { 1 } , \alpha _ { 2 } \cup \gamma , \ldots , \alpha _ { q } ) , \ldots ,$ $( \alpha _ { 1 } , \alpha _ { 2 } , \ldots , \alpha _ { q } \cup \gamma ) \in \mathcal{F} ( S ) ^ { q }$ all have the same colour.

Introduced originally in [a1] as a tool for analyzing certain types of games (cf. also Games, theory of), the Hales–Jewett theorem was soon recognized as a cornerstone of Ramsey theory. Among the numerous corollaries of the Hales–Jewett theorem one has the van der Waerden theorem on arithmetic progressions and its multi-dimensional version (the Gallai theorem). For example, to see that the Hales–Jewett theorem implies the van der Waerden theorem, take $A = \{ 0 , \dots , q - 1 \}$ and interpret the words over $A$ as base-$q$ expansions. If $w ( t )$ is a variable word over $A \cup \{ t \}$, then $\{ w ( a ) \} _ { a \in A }$ is a length-$q$ arithmetic progression in $\mathbf{N}$. Also, in [a3] the Hales–Jewett theorem has been used to provide a significantly simplified proof of the geometric Ramsey theorem due to R. Graham, K. Leeb and B. Rothschild ([a2]). See [a4] for more details and discussion.

The Furstenberg–Katznelson density Hales–Jewett theorem ([a5]), which confirmed a conjecture made by Graham and which bears the same relation to the Hales–Jewett theorem as the Szemerédi theorem on arithmetic progressions bears to van der Waerden's theorem, states that for any $q \in \mathbf{N}$ and $\varepsilon > 0$ there exists an $M = M ( q , \varepsilon )$ so that if $n \geq M$, $A$ is a $q$-element set and $R \subseteq A ^ { n }$ satisfies $| R | > \varepsilon q ^ { n }$, then $R$ contains a combinatorial line.

A polynomial extension of the Hales–Jewett theorem was obtained in [a6], where it was shown that for any $q , r , d \in \mathbf{N}$ there exists an $N = N ( q , r , d )$ so that if $S$ is a set with $ \geq N$ elements, then for any $r$-colouring of $\mathcal{F} ( S ^ { d } ) ^ { q }$ there exist a non-empty set $\gamma \in {\cal F} ( S )$ and sets $\alpha _ 1 , \dots , \alpha _ { q } \in \mathcal{F} ( S ^ { d } )$ such that $\gamma ^ { d } \cap \alpha _ { 1 } = \ldots = \gamma ^ { d } \cap \alpha _ { q } = \emptyset$ and such that $( \alpha _ { 1 } , \dots , \alpha _ { q } ), ( \alpha _ { 1 } \cup \gamma ^ { d } , \alpha _ { 2 } , \dots , \alpha _ { q } ), ( \alpha _ { 1 } , \alpha _ { 2 } \cup \gamma ^ { d } , \dots , \alpha _ { q } ), \cdots, ( \alpha _ { 1 } , \alpha _ { 2 } , \dots , \alpha _ { q } \cup \gamma ^ { d } ) \in {\cal F} ( S ^ { d } ) ^ { q }$ all have the same colour. The method utilized in [a6] is that of topological dynamics; see [a7] or [a8] for a purely combinatorial proof. See [a9], [a10], [a11] for applications of the polynomial Hales–Jewett theorem to density Ramsey theory.

Infinitary generalizations of the Hales–Jewett theorem were obtained in [a12], [a13], [a14] and [a15]. For an infinitary version of the polynomial Hales–Jewett theorem, see [a7], Sect. 2.6.

For a proof of the Hales–Jewett theorem which yields a primitive recursive upper bound for $N ( q , r )$, see [a16] or [a17].

It is conjectured that the polynomial Hales–Jewett theorem should admit a density generalization. See [a18], p. 57, for a formulation.

References

[a1]	A.W. Hales, R.I. Jewett, "Regularity and positional games" Trans. Amer. Math. Soc. , 106 (1963) pp. 222–229
[a2]	R. Graham, K. Leeb, B. Rothschild, "Ramsey's theorem for a class of categories" Adv. Math. , 8 (1972) pp. 417–433
[a3]	J. Spencer, "Ramsey's theorem for spaces" Trans. Amer. Math. Soc. , 249 (1979) pp. 363–371
[a4]	R. Graham, B. Rothschild, J. Spencer, "Ramsey theory" , Wiley (1980)
[a5]	H. Furstenberg, Y. Katznelson, "A density version of the Hales–Jewett theorem" J. d'Anal. Math. , 57 (1991) pp. 64–119
[a6]	V. Bergelson, A. Leibman, "Set-polynomials and polynomial extensions of the Hales–Jewett theorem" Ann. of Math. (2) , 150 : 1 (1999) pp. 33–75
[a7]	R. McCutcheon, "Elemental methods in ergodic Ramsey theory" , Lecture Notes in Mathematics , 1722 , Springer (1999)
[a8]	M. Walters, "Combinatorial proofs of the polynomial van der Waerden theorem and the polynomial Hales–Jewett theorem" J. London Math. Soc. (2) , 61 : 1 (2000) pp. 1–12
[a9]	V. Bergelson, R. McCutcheon, "Uniformity in polynomial Szemerédi theorem" M. Pollicott (ed.) K. Schmidt (ed.) , Ergodic Theory of ${\bf Z} ^ { d }$-actions , Lecture Notes , 228 , London Math. Soc. (1996) pp. 273–296
[a10]	A. Leibman, "Multiple recurrence theorem for measure preserving actions of a nilpotent group" Geom. Funct. Anal. , 8 (1998) pp. 853–931
[a11]	V. Bergelson, R. McCutcheon, "A polynomial IP Szemerédi theorem for finite families of commuting transformations" , Memoirs , Amer. Math. Soc. (to appear)
[a12]	T. Carlson, S. Simpson, "A dual form of Ramsey's theorem" Adv. Math. , 53 (1984) pp. 265–290
[a13]	T. Carlson, "Some unifying principles in Ramsey theory" Discr. Math. , 68 (1988) pp. 117–169
[a14]	H. Furstenberg, Y. Katznelson, "Idempotents in compact semigroups and Ramsey theory" Israel J. Math. , 68 (1990) pp. 257–270
[a15]	V. Bergelson, A. Blass, N. Hindman, "Partition theorems for spaces of variable words" Proc. London Math. Soc. , 68 (1994) pp. 449–476
[a16]	S. Shelah, "Primitive recursive bounds for van der Waerden numbers" J. Amer. Math. Soc. , 1 : 3 (1988) pp. 683–697
[a17]	A. Nilli, "Shelah's proof of the Hales–Jewett theorem" , Mathematics of Ramsey theory (Algorithms Combin.) , 5 , Springer (1990) pp. 150–151
[a18]	V. Bergelson, "Ergodic Ramsey theory — An update" M. Pollicott (ed.) K. Schmidt (ed.) , Ergodic Theory of ${\bf Z} ^ { d }$-actions , Lecture Notes , 228 , London Math. Soc. (1996) pp. 1–61