Large minimal sets which force arithmetic progressions
type: Item
instance of: scholarly article
title: Large minimal sets which force arithmetic progressions
zbMATH Open document ID: 0604.05003
DOI: 10.1016/0097-3165(86)90097-X
author: Ron Graham
author: J. Nešetřil
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. Wisk. 15, 212-216 (1927; JFM 53.0073.12)], if \(N=\{1,2,3,...\}=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 asserts the following: For all k,r\(\in N\), there exists a least integer W(k,r) so that if \(\{1,2,3,...,W(k,r)\}=C_ 1\cup...\cup C_ r\) then some \(C_ i\) must contain a k-term arithmetic progression. For k,r\(\in N\) and \(X\subseteq N\), let us write \(X\to AP(k)_ r\) to denote the fact that for any partition of \(X=C_ 1\cup...\cup C_ r\), some \(C_ i\) contains a k-term arithmetic progression. X is said to be \(AP(k)_ r\)- critical if \(X\to AP(k)_ r\) but \(Y\nrightarrow AP(k)_ r\) for any proper subset \(Y\subset X\). In the paper under review, the authors prove the existence of arbitrarily large \(AP(k)_ r\)-critical sets for \(k\geq 3\). The main result yields arbitrarily large critical sets for more general combinatorial lines. For a fixed finite set A, call a subset \(L\subseteq A^ n\) a combinatorial line if for some nonempty \(I\subseteq \{1,2,...,n\}\), L can be written as \(L=\cup_{a\in A}\{(x_ 1,...,x_ n):\) \(x_ i=a\) if \(i\in I\) and \(x_ i=b_ i\in A\) if \(i\not\in I\}\). For a subset \(X\subseteq A^ n\), let us write \(X\to (line)_ r\) if for any partition of \(X=C_ 1\cup...\cup C_ r\), some \(C_ i\) must contain a combinatorial line. According to the basic theorem of \textit{A. W. Hales} and \textit{R. I. Jewett} [Trans. Am. Math. Soc. 106, 222-229 (1963; Zbl 0113.148)], for all finite A and \(r\in N\), there exists an n(A,r) such that if \(n\geq n(A,r)\) then \(A^ n\to (line)_ r\). (It is well known that the Hales-Jewett theorem implies not only the theorem of van der Waerden but also its generalizations to higher dimensions.) The main result of the paper is the following theorem: For every A, a, and r with \(| A| =k\geq 3\), if \(n\geq n^*(A,a,r)\) then the…
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 11B25
zbMATH DE Number: 3974962
zbMATH Keywords: partitions
zbMATH Keywords: Ramsey theory
zbMATH Keywords: arithmetic progressions
zbMATH Keywords: van der Waerden's theorem
zbMATH Keywords: critical sets
zbMATH Keywords: combinatorial lines
reviewed by: Mihály Szalay
MaRDI profile type: Publication
cites work: A Construction for Partitions Which Avoid Long Arithmetic Progressions
cites work: Q3863921
cites work: Partitionen und lineare Gleichungssysteme
cites work: Graph Theory and Probability
cites work: Q4400998
cites work: Q3903002
cites work: Regularity and Positional Games
cites work: Parallel concepts in graph theory
cites work: Q4113906
cites work: Studien zur Kombinatorik
cites work: Restricted Ramsey configurations
cites work: Ein kombinatorischer Satz der Elementargeometrie
Recommended article: Arithmetic Progressions in Sets with Small Sumsets
Recommended article: Maximal subsets free of arithmetic progressions in arbitrary sets
Recommended article: Long arithmetic progressions in critical sets
Recommended article: Large sets avoiding Infinite arithmetic / geometric progressions
Recommended article: Almost Arithmetic Progressions in the Primes and Other Large Sets
Recommended article: Arithmetic progressions in lacunary sets
Recommended article: Long Arithmetic Progressions in Small Sumsets
Recommended article: Dimensions of Sets Which Uniformly Avoid Arithmetic Progressions
Recommended article: Arithmetic progressions in sums of subsets of sparse sets
Recommended article: Arithmetic progressions in sumsets of sparse sets
description: scientific article; zbMATH DE number 3974962