Namespaces
Variants
Actions

Difference between revisions of "Hales-Jewett theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (AUTOMATIC EDIT (latexlist): Replaced 82 formulas out of 83 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 83 formulas, 82 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|partial}}
 
''Jewett–Hales theorem''
 
''Jewett–Hales theorem''
  
 
One of the fundamental results in Ramsey theory.
 
One of the fundamental results in Ramsey theory.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h1300201.png" /> be a finite [[Alphabet|alphabet]] and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h1300202.png" /> denote the set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h1300203.png" />-tuples with entries from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h1300204.png" />. A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h1300205.png" /> consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h1300206.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h1300207.png" />-tuples <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h1300208.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h1300209.png" />, is a combinatorial line if there exists a non-empty subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002010.png" /> such that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002012.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002013.png" /> and for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002014.png" /> one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002015.png" />. An alternative way of describing a combinatorial line is the following. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002016.png" /> be a  "variable" . A variable word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002017.png" /> is a word over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002018.png" /> in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002019.png" /> occurs. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002020.png" />, denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002021.png" /> the word which results from replacing each occurrence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002022.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002023.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002024.png" />. Then the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002025.png" /> is a combinatorial line. For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002027.png" /> then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002028.png" /> is a combinatorial line in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002029.png" />.
+
Let $A = \{ a _ { 1 } , \dots , a _ { q } \}$ be a finite [[Alphabet|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 [[#References|[a1]]], states that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002030.png" /> there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002031.png" /> such that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002032.png" /> is partitioned into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002033.png" /> classes, then at least one of these classes contains a combinatorial line.
+
The Hales–Jewett theorem, proved in [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002034.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002035.png" /> denote the set of all finite subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002036.png" />. For any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002037.png" /> there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002038.png" /> so that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002039.png" /> is a set with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002040.png" /> elements, then for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002041.png" />-colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002042.png" /> there exist a non-empty set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002043.png" /> and sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002044.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002045.png" /> and such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002046.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002047.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002048.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002049.png" /> all have the same colour.
+
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 [[#References|[a1]]] as a tool for analyzing certain types of games (cf. also [[Games, theory of|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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002050.png" /> and interpret the words over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002051.png" /> as base-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002052.png" /> expansions. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002053.png" /> is a variable word over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002054.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002055.png" /> is a length-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002056.png" /> arithmetic progression in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002057.png" />. Also, in [[#References|[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 ([[#References|[a2]]]). See [[#References|[a4]]] for more details and discussion.
+
Introduced originally in [[#References|[a1]]] as a tool for analyzing certain types of games (cf. also [[Games, theory of|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|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 [[#References|[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 ([[#References|[a2]]]). See [[#References|[a4]]] for more details and discussion.
  
The Furstenberg–Katznelson density Hales–Jewett theorem ([[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002058.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002059.png" /> there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002060.png" /> so that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002062.png" /> is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002063.png" />-element set and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002064.png" /> satisfies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002065.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002066.png" /> contains a combinatorial line.
+
The Furstenberg–Katznelson density Hales–Jewett theorem ([[#References|[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 &gt; 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 | &gt; \varepsilon q ^ { n }$, then $R$ contains a combinatorial line.
  
A polynomial extension of the Hales–Jewett theorem was obtained in [[#References|[a6]]], where it was shown that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002067.png" /> there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002068.png" /> so that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002069.png" /> is a set with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002070.png" /> elements, then for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002071.png" />-colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002072.png" /> there exist a non-empty set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002073.png" /> and sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002074.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002075.png" /> and such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002076.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002077.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002078.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002079.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002080.png" /> all have the same colour. The method utilized in [[#References|[a6]]] is that of [[Topological dynamics|topological dynamics]]; see [[#References|[a7]]] or [[#References|[a8]]] for a purely combinatorial proof. See [[#References|[a9]]], [[#References|[a10]]], [[#References|[a11]]] for applications of the polynomial Hales–Jewett theorem to density Ramsey theory.
+
A polynomial extension of the Hales–Jewett theorem was obtained in [[#References|[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 } )$, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002079.png"/>, $( \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 [[#References|[a6]]] is that of [[Topological dynamics|topological dynamics]]; see [[#References|[a7]]] or [[#References|[a8]]] for a purely combinatorial proof. See [[#References|[a9]]], [[#References|[a10]]], [[#References|[a11]]] for applications of the polynomial Hales–Jewett theorem to density Ramsey theory.
  
 
Infinitary generalizations of the Hales–Jewett theorem were obtained in [[#References|[a12]]], [[#References|[a13]]], [[#References|[a14]]] and [[#References|[a15]]]. For an infinitary version of the polynomial Hales–Jewett theorem, see [[#References|[a7]]], Sect. 2.6.
 
Infinitary generalizations of the Hales–Jewett theorem were obtained in [[#References|[a12]]], [[#References|[a13]]], [[#References|[a14]]] and [[#References|[a15]]]. For an infinitary version of the polynomial Hales–Jewett theorem, see [[#References|[a7]]], Sect. 2.6.
  
For a proof of the Hales–Jewett theorem which yields a primitive recursive upper bound for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002081.png" />, see [[#References|[a16]]] or [[#References|[a17]]].
+
For a proof of the Hales–Jewett theorem which yields a primitive recursive upper bound for $N ( q , r )$, see [[#References|[a16]]] or [[#References|[a17]]].
  
 
It is conjectured that the polynomial Hales–Jewett theorem should admit a density generalization. See [[#References|[a18]]], p. 57, for a formulation.
 
It is conjectured that the polynomial Hales–Jewett theorem should admit a density generalization. See [[#References|[a18]]], p. 57, for a formulation.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.W. Hales,  R.I. Jewett,  "Regularity and positional games"  ''Trans. Amer. Math. Soc.'' , '''106'''  (1963)  pp. 222–229</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R. Graham,  K. Leeb,  B. Rothschild,  "Ramsey's theorem for a class of categories"  ''Adv. Math.'' , '''8'''  (1972)  pp. 417–433</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Spencer,  "Ramsey's theorem for spaces"  ''Trans. Amer. Math. Soc.'' , '''249'''  (1979)  pp. 363–371</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Graham,  B. Rothschild,  J. Spencer,  "Ramsey theory" , Wiley  (1980)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  H. Furstenberg,  Y. Katznelson,  "A density version of the Hales–Jewett theorem"  ''J. d'Anal. Math.'' , '''57'''  (1991)  pp. 64–119</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  V. Bergelson,  A. Leibman,  "Set-polynomials and polynomial extensions of the Hales–Jewett theorem"  ''Ann. of Math. (2)'' , '''150''' :  1  (1999)  pp. 33–75</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R. McCutcheon,  "Elemental methods in ergodic Ramsey theory" , ''Lecture Notes in Mathematics'' , '''1722''' , Springer  (1999)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  V. Bergelson,  R. McCutcheon,  "Uniformity in polynomial Szemerédi theorem"  M. Pollicott (ed.)  K. Schmidt (ed.) , ''Ergodic Theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002082.png" />-actions'' , ''Lecture Notes'' , '''228''' , London Math. Soc.  (1996)  pp. 273–296</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  A. Leibman,  "Multiple recurrence theorem for measure preserving actions of a nilpotent group"  ''Geom. Funct. Anal.'' , '''8'''  (1998)  pp. 853–931</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  V. Bergelson,  R. McCutcheon,  "A polynomial IP Szemerédi theorem for finite families of commuting transformations" , ''Memoirs'' , Amer. Math. Soc.  (to appear)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  T. Carlson,  S. Simpson,  "A dual form of Ramsey's theorem"  ''Adv. Math.'' , '''53'''  (1984)  pp. 265–290</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  T. Carlson,  "Some unifying principles in Ramsey theory"  ''Discr. Math.'' , '''68'''  (1988)  pp. 117–169</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  H. Furstenberg,  Y. Katznelson,  "Idempotents in compact semigroups and Ramsey theory"  ''Israel J. Math.'' , '''68'''  (1990)  pp. 257–270</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  V. Bergelson,  A. Blass,  N. Hindman,  "Partition theorems for spaces of variable words"  ''Proc. London Math. Soc.'' , '''68'''  (1994)  pp. 449–476</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  S. Shelah,  "Primitive recursive bounds for van der Waerden numbers"  ''J. Amer. Math. Soc.'' , '''1''' :  3  (1988)  pp. 683–697</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  A. Nilli,  "Shelah's proof of the Hales–Jewett theorem" , ''Mathematics of Ramsey theory (Algorithms Combin.)'' , '''5''' , Springer  (1990)  pp. 150–151</TD></TR><TR><TD valign="top">[a18]</TD> <TD valign="top">  V. Bergelson,  "Ergodic Ramsey theory — An update"  M. Pollicott (ed.)  K. Schmidt (ed.) , ''Ergodic Theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h130/h130020/h13002083.png" />-actions'' , ''Lecture Notes'' , '''228''' , London Math. Soc.  (1996)  pp. 1–61</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  A.W. Hales,  R.I. Jewett,  "Regularity and positional games"  ''Trans. Amer. Math. Soc.'' , '''106'''  (1963)  pp. 222–229</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  R. Graham,  K. Leeb,  B. Rothschild,  "Ramsey's theorem for a class of categories"  ''Adv. Math.'' , '''8'''  (1972)  pp. 417–433</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  J. Spencer,  "Ramsey's theorem for spaces"  ''Trans. Amer. Math. Soc.'' , '''249'''  (1979)  pp. 363–371</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  R. Graham,  B. Rothschild,  J. Spencer,  "Ramsey theory" , Wiley  (1980)</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  H. Furstenberg,  Y. Katznelson,  "A density version of the Hales–Jewett theorem"  ''J. d'Anal. Math.'' , '''57'''  (1991)  pp. 64–119</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  V. Bergelson,  A. Leibman,  "Set-polynomials and polynomial extensions of the Hales–Jewett theorem"  ''Ann. of Math. (2)'' , '''150''' :  1  (1999)  pp. 33–75</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  R. McCutcheon,  "Elemental methods in ergodic Ramsey theory" , ''Lecture Notes in Mathematics'' , '''1722''' , Springer  (1999)</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  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</td></tr><tr><td valign="top">[a10]</td> <td valign="top">  A. Leibman,  "Multiple recurrence theorem for measure preserving actions of a nilpotent group"  ''Geom. Funct. Anal.'' , '''8'''  (1998)  pp. 853–931</td></tr><tr><td valign="top">[a11]</td> <td valign="top">  V. Bergelson,  R. McCutcheon,  "A polynomial IP Szemerédi theorem for finite families of commuting transformations" , ''Memoirs'' , Amer. Math. Soc.  (to appear)</td></tr><tr><td valign="top">[a12]</td> <td valign="top">  T. Carlson,  S. Simpson,  "A dual form of Ramsey's theorem"  ''Adv. Math.'' , '''53'''  (1984)  pp. 265–290</td></tr><tr><td valign="top">[a13]</td> <td valign="top">  T. Carlson,  "Some unifying principles in Ramsey theory"  ''Discr. Math.'' , '''68'''  (1988)  pp. 117–169</td></tr><tr><td valign="top">[a14]</td> <td valign="top">  H. Furstenberg,  Y. Katznelson,  "Idempotents in compact semigroups and Ramsey theory"  ''Israel J. Math.'' , '''68'''  (1990)  pp. 257–270</td></tr><tr><td valign="top">[a15]</td> <td valign="top">  V. Bergelson,  A. Blass,  N. Hindman,  "Partition theorems for spaces of variable words"  ''Proc. London Math. Soc.'' , '''68'''  (1994)  pp. 449–476</td></tr><tr><td valign="top">[a16]</td> <td valign="top">  S. Shelah,  "Primitive recursive bounds for van der Waerden numbers"  ''J. Amer. Math. Soc.'' , '''1''' :  3  (1988)  pp. 683–697</td></tr><tr><td valign="top">[a17]</td> <td valign="top">  A. Nilli,  "Shelah's proof of the Hales–Jewett theorem" , ''Mathematics of Ramsey theory (Algorithms Combin.)'' , '''5''' , Springer  (1990)  pp. 150–151</td></tr><tr><td valign="top">[a18]</td> <td valign="top">  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</td></tr></table>

Revision as of 17:03, 1 July 2020

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 } )$, , $( \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
How to Cite This Entry:
Hales-Jewett theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hales-Jewett_theorem&oldid=22541
This article was adapted from an original article by V. Bergelson (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article