A density version of the Hales-Jewett theorem
type: Item
instance of: scholarly article
title: A density version of the Hales-Jewett theorem
zbMATH Open document ID: 0770.05097
DOI: 10.1007/BF03041066
author: Yitzhak Katznelson
author: Hillel Furstenberg
published in: Journal d'Analyse Mathématique
publication date: 1993-06-29T00:00:00Z
review text: The theorem of van der Waerden on arithmetic progressions states that for given natural numbers \(r,k\) there is a constant \(K(r,k)\) so that for any partition of an arithmetic progression of length \(K\geq K(r,k)\) to \(r\) subsets, one of these contains an arithmetic progression of length \(k\). This result is the prototype of a Ramsey theorem whereby a certain kind of structure is reproduced in small scale when a large scale model is partitioned arbitrarily to a fixed number of subsets. Van der Waerden's theorem is a special case of a general combinatorial theorem proved by Hales and Jewett. To formulate their result we make some definitions. Let \(A\) denote a finite set \(\{a_ 1,a_ 2,\dots,a_ k\}\), and let \(W_ N(A)\) denote the words of length \(N\) with letters in \(A\), \(W_ N(A)=A^ N\). We think of the points of \(W_ N(A)\) as vectors in a ``combinatorial'' \(N\)-dimensional space. If \(A\) is a finite field, then \(W_ N(A)\) is indeed a vector space over \(A\). This example motivates the following definition of a ``line'' in \(W_ N(A)\): if \(k=\#(A)\) then \(k\) points \(\{w^ 1,w^ 2,\dots,w^ k\}\) in \(W_ N(A)\) constitute a combinatorial line if there is a partition \(\{1,2,\dots,N\}=I\cup J\), \(I\cap J=\varnothing\), \(J\neq\varnothing\) and writing \(w^ h=(w^ h_ 1,w^ h_ 2,\dots,w^ h_ N)\) we have \(w^ 1_ n=w^ 2_ n=\cdots=w^ k_ n\) for \(n\in I\), and \(w^ h_ n=a_ h\) for \(n\in J\). We can also describe \(\{w^ 1,w^ 2,\dots,w^ k\}\) as follows. Let \(x\) denote a variable and form words with the alphabet \(A\cup x\). Suppose \(w(x)\) is such a word in which the letter \(x\) occurs. Then \(w(1)\), \(w(2),\dots,w(k)\) form a combinatorial line. Note that if \(A\) is a finite field then a combinatorial line is a line in the geometric sense in the vector space \(A^ N\). Moreover if \(A=\{0,1,\dots,k-1\}\) and we interpret \(W_ N(A)\) as integers \(<k^ N\), then a combinatorial line forms an arithmetic progression. The Hales-Jewett theorem can now be form…
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 11B25
Mathematics Subject Classification ID: 05A18
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 60E99
zbMATH DE Number: 221305
zbMATH Keywords: arithmetic progression
zbMATH Keywords: Ramsey theorem
zbMATH Keywords: combinatorial line
zbMATH Keywords: Hales-Jewett theorem
zbMATH Keywords: partition
zbMATH Keywords: van der Waerden's theorem
zbMATH Keywords: coloring theorem
Wikidata QID: Q55879050
MaRDI profile type: Publication
cites work: Some unifying principles in Ramsey theory
cites work: A dual form of Ramsey's theorem
cites work: Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions
cites work: Q3909268
cites work: An ergodic Szemerédi theorem for commuting transformations
cites work: An ergodic Szemerédi theorem for IP-systems and combinatorial theory
cites work: A density version of the Hales-Jewett theorem for \(k=3\)
cites work: Idempotents in compact semigroups and Ramsey theory
cites work: The ergodic theoretical proof of Szemerédi’s theorem
cites work: Regularity and Positional Games
cites work: On sets of integers containing k elements in arithmetic progression
description: scientific article; zbMATH DE number 221305