Large minimal sets which force arithmetic progressions
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 there exists \(X\subseteq A^ n\) such that \(X\to (line)_ r\) and \(X'\nrightarrow (line)_ r\) for every X'\(\subseteq X\) with \(| X'| <a\). This theorem implies the existence of arbitrarily large \((line)_ r\)-critical sets in \(A^ n\) for every A and r with \(| A| =k\geq 3\) and sufficiently large n.
scientific article; zbMATH DE number 3974962
scientific article