×

zbMATH — the first resource for mathematics

Primitive recursive bounds for van der Waerden numbers. (English) Zbl 0649.05010
The author solves one of the most outstanding and notorious problems of combinatorics by exhibiting primitive recursive bounds on the van der Waerden numbers. All earlier proofs gave Ackermann-like bounds and the question on the existence of primitive recursive bounds was posed by Solovay, and widely popularized by Erdős, Graham, and others. “Only time will tell, and we may not be here to listen, what the truth is” wrote Graham on the problem [R. L. Graham; Rudiments of Ramsey theory (1981; Zbl 0458.05043)]. We are here and eagerly listening to the amazingly simple solution presented here.
If n is the length of the arithmetical progression to be found, c is the number of colors, the orthodox proofs for the case (n,c) used the case (n-1,d) where d is a very large number. This double induction is responsible for the Ackermann-like growth. The proof here presented uses only simple induction, i.e. the case (n,c) is deduced from the case (n- 1,c). A relatively simple Ramsey type lemma is used, for which the application of the pidgeonhole principle gives superexponential but primitive recursive bounds. Then, the Hales-Jewett theorem is deduced, along with the Graham-Rothschild higher dimensional generalization and the affine Ramsey theorem on monocolored subspaces. This important problem on van der Waerden numbers though resolved the real behaviour of the growth of this function still remains a mystery.
Reviewer: P.Komjáth

MSC:
05A99 Enumerative combinatorics
05C55 Generalized Ramsey theory
11B25 Arithmetic progressions
15A03 Vector spaces, linear dependence, rank, lineability
03D20 Recursive functions and relations, subrecursive hierarchies
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Wilhelm Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann. 99 (1928), no. 1, 118 – 133 (German). · JFM 54.0056.06 · doi:10.1007/BF01459088 · doi.org
[2] E. R. Berlekamp, A construction for partitions which avoid long arithmetic progressions., Canad. Math. Bull. 11 (1968), 409 – 414. · Zbl 0169.31905 · doi:10.4153/CMB-1968-047-7 · doi.org
[3] P. Erdös and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc. (3) 2 (1952), 417 – 439. · Zbl 0048.28203 · doi:10.1112/plms/s3-2.1.417 · doi.org
[4] H. Furstenberg, Recurrence in ergodic theory and combinatorial number theory, Princeton University Press, Princeton, N.J., 1981. M. B. Porter Lectures. · Zbl 0459.28023
[5] R. L. Graham, K. Leeb, and B. L. Rothschild, Ramsey’s theorem for a class of categories, Proc. Nat. Acad. Sci. U.S.A. 69 (1972), 119 – 120. R. L. Graham, K. Leeb, and B. L. Rothschild, Ramsey’s theorem for a class of categories, Advances in Math. 8 (1972), 417 – 433. · Zbl 0243.18011 · doi:10.1016/0001-8708(72)90005-9 · doi.org
[6] R. L. Graham and V. Rödl, Numbers in Ramsey theory, Surveys in combinatorics 1987 (New Cross, 1987) London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 111 – 153. · Zbl 0633.05049
[7] R. L. Graham and B. L. Rothschild, Ramsey’s theorem for \?-parameter sets, Trans. Amer. Math. Soc. 159 (1971), 257 – 292. · Zbl 0233.05003
[8] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, John Wiley & Sons, Inc., New York, 1980. Wiley-Interscience Series in Discrete Mathematics; A Wiley-Interscience Publication. · Zbl 0455.05002
[9] A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222 – 229. · Zbl 0113.14802
[10] Jussi Ketonen and Robert Solovay, Rapidly growing Ramsey functions, Ann. of Math. (2) 113 (1981), no. 2, 267 – 314. · Zbl 0494.03027 · doi:10.2307/2006985 · doi.org
[11] H. E. Rose, Subrecursion: functions and hierarchies, Oxford Logic Guides, vol. 9, The Clarendon Press, Oxford University Press, New York, 1984. · Zbl 0539.03018
[12] K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104 – 109. · Zbl 0050.04002 · doi:10.1112/jlms/s1-28.1.104 · doi.org
[13] Joel H. Spencer, Ramsey’s theorem for spaces, Trans. Amer. Math. Soc. 249 (1979), no. 2, 363 – 371. · Zbl 0387.05018
[14] E. Szemerédi, On sets of integers containing no \? elements in arithmetic progression, Acta Arith. 27 (1975), 199 – 245. Collection of articles in memory of Juriĭ Vladimirovič Linnik. · Zbl 0303.10056
[15] B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wisk. 15 (1927), 212-216. · JFM 53.0073.12
[16] Bernd Voigt, The partition problem for finite abelian groups, J. Combin. Theory Ser. A 28 (1980), no. 3, 257 – 271. · Zbl 0442.05003 · doi:10.1016/0097-3165(80)90069-2 · doi.org
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.