An elementary proof of the canonizing version of Gallai-Witt's theorem
type: Item
instance of: scholarly article
title: An elementary proof of the canonizing version of Gallai-Witt's theorem
zbMATH Open document ID: 0589.05010
DOI: 10.1016/0097-3165(86)90014-2
author: Hans Jürgen Prömel
author: Vojtěch Rödl
published in: Journal of Combinatorial Theory. Series A
publication date: 1986-01-01T00:00:00Z
review text: According to the classical theorem of \textit{B. L. van der Waerden} [Nieuw Arch. Wiskd. 15, 212-216 (1927; JFM 53.0073.12)], if \(N=\{0,1,2,...\}=C_ 1\cup...\cup C_ r\) then for some i, \(C_ i\) contains arbitrarily long arithmetic progressions. The finite form of van der Waerden's theorem (for two classes) asserts the following: For all \(k\in N\setminus \{0\}\), there exists a least n(k) so that if \(\{0,1,2,...,n(k)-1\}=C_ 1\cup C_ 2\) then some \(C_ i\) must contain a k-term arithmetic progression. A multi-dimensional version of van der Waerden's theorem is independently due to T. Gallai (see \textit{R. Radó} [Math. Z. 36, 424-480 (1933; Zbl 0006.14603)]) and to \textit{E. Witt} [Math. Nachr. 6, 261-262 (1951)]. It asserts that for every mapping \(\Delta\) :\(\{0,...,n-1\}^ t\to \{0,1\}\), where \(n\geq n(t,k)\) is sufficiently large, there exists a homothety \(h: N^ t\to N^ t\) \((h(x)=a+dx\), \(a\in N^ t\), \(d\in N\setminus \{0\})\) such that \(\Delta (h(b))=\Delta (h(c))\) for all \(b,c\in \{0,...,k-1\}^ t\). The following result of \textit{P. Erdős} and \textit{R. L. Graham} [Old and new problems and results in combinatorial number theory (Monographie 28, L'Enseignement Mathématique, Genève) (1980; Zbl 0434.10001)] is called the canonical version of van der Waerden's theorem. For every mapping \(\Delta\) :\(\{\) 0,...,n-1\(\}\) \(\to N\), where \(n\geq n_ 0(k)\) is sufficiently large, there exists a k-term arithmetic progression \(P\subseteq \{0,...,n-1\}\) such that \(\Delta_{| P}\) is either a constant mapping or a one-to-one mapping (i.e., there are two ''canonical types'' for \(\Delta_{| P}).\) A vector \(b\in Q^ t\) is called admissible for \(S\subseteq N^ t\) iff there exists a vector \(a\in Q^ t\) such that the affine line \(\{a+\lambda b| \lambda \in Q\}\) intersects S in at least two points. Let \({\mathcal A}(S)\) denote the set of linear subspaces of \(Q^ t\) possessing a basis of admissible vectors. Additionally the null-space \(\{\) \(0\}\) be…
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 11B25
zbMATH DE Number: 3946137
zbMATH Keywords: canonical partitions
zbMATH Keywords: multidimensional analogues of van der
zbMATH Keywords: Waerden's theorem on arithmetic progressions
zbMATH Keywords: Ramsey theory
reviewed by: Mihály Szalay
MaRDI profile type: Publication
full work available at URL: 0097-3165(86)90014-2
OpenAlex ID: W1981032837
cites work: A canonical partition theorem for equivalence relations on \(Z^ n\).
cites work: Der Satz von van der Waerden über arithmetische Progressionen
cites work: An ergodic Szemerédi theorem for commuting transformations
cites work: Q3689195
cites work: Q3903002
cites work: Canonical configurations
Recommended article: A canonical restricted version of van der Waerden's theorem
Recommended article: A Short Proof of van der Waerden's Theorem on Arithmetic Progressions
Recommended article: Recursively enumerable sets and van der Waerden's theorem on arithmetic progressions
Recommended article: On van der Waerden's theorem on arithmetic progressions
Recommended article: An algebraic proof of van der Waerden's theorem
Recommended article: Q4304347
Recommended article: Monochromatic arithmetic progressions with large differences
Recommended article: An application of Lovász' local lemma-A new lower bound for the van der Waerden number
Recommended article: Q3480041
Recommended article: Q4860060
description: scientific article; zbMATH DE number 3946137