Hales-Jewett theorem
Jewett–Hales theorem
One of the fundamental results in Ramsey theory.
Let be a finite alphabet and let
denote the set of
-tuples with entries from
. A set
consisting of
-tuples
,
, is a combinatorial line if there exists a non-empty subset
such that for
and
one has
and for
one has
. An alternative way of describing a combinatorial line is the following. Let
be a "variable" . A variable word
is a word over the alphabet
in which
occurs. For
, denote by
the word which results from replacing each occurrence of
in
by
. Then the set
is a combinatorial line. For example, if
and
then
is a combinatorial line in
.
The Hales–Jewett theorem, proved in [a1], states that for any there exists an
such that if
is partitioned into
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 , let
denote the set of all finite subsets of
. For any
there exists an
so that if
is a set with
elements, then for any
-colouring of
there exist a non-empty set
and sets
such that
and such that
,
,
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 and interpret the words over
as base-
expansions. If
is a variable word over
, then
is a length-
arithmetic progression in
. 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 and
there exists an
so that if
,
is a
-element set and
satisfies
, then
contains a combinatorial line.
A polynomial extension of the Hales–Jewett theorem was obtained in [a6], where it was shown that for any there exists an
so that if
is a set with
elements, then for any
-colouring of
there exist a non-empty set
and sets
such that
and such that
,
,
,
,
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 , 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 ![]() |
[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 ![]() |
Hales-Jewett theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hales-Jewett_theorem&oldid=22541