Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T02:56:59.642Z Has data issue: false hasContentIssue false
  • English
  • Français

Monochromatic sequences whose gaps belong to {d, 2d, …, md}

Published online by Cambridge University Press:  17 April 2009

Bruce M. Landman
Bruce M. Landman
Affiliation:
Department of Mathematical Sciences, University of North Carolina at Greensboro, Greensboro, NC 27412, United States of America e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

For m and k positive integers, define a k-term hm-progression to be a sequence of positive integers {x1,…,xk} such that for some positive integer d, xi + 1 − xi ∈ {d, 2d,…, md} for i = 1,…, k - 1. Let hm(k) denote the least positive integer n such that for every 2-colouring of {1, 2, …, n} there is a monochromatic hm-progression of length k. Thus, h1(k) = w(k), the classical van der Waerden number. We show that, for 1 ≤ r ≤ m, hm(m + r) ≤ 2c(m + r − 1) + 1, where c = ⌈m/(m − r)⌉. We also give a lower bound for hm(k) that has order of magnitude 2k2/m. A precise formula for hm(k) is obtained for all m and k such that k ≤ 3m/2.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 58 , Issue 1 , August 1998 , pp. 93 - 101
Copyright
Copyright © Australian Mathematical Society 1998

References

[1]Brown, T.C., Erdős, P. and Freedman, A.R., ‘Quasi-progressions and descending waves’, J. Comb. Theory Ser. A 53 (1990), 81–95.CrossRefGoogle Scholar
[2]Brown, T.C. and Hare, D.R., ‘Arithmetic progressions in sequences with bounded gaps’, J. Comb. Theory Ser. A 77 (1997), 222–227.CrossRefGoogle Scholar
[3]Chvátal, V. Some unknown van der Waerden numbers, in Combinatorial structures and their applications, (Guy, R.K. et al. , Editors) (Gordon and Breach, New York, 1970), pp. 31–33.Google Scholar
[4]Graham, R.L., Rothschild, B.L., and Spencer, J.H., Ramsey theory, (2nd ed.) (John Wiley and Sons, New York, 1990).Google Scholar
[5]Greenwell, R.N. and Landman, B.M., ‘On the existence of a reasonable upper bound for the van der Waerden numbers’, J. Combin. Theory Ser. A 50 (1989), 82–86.CrossRefGoogle Scholar
[6]Landman, B.M., ‘Generalized van der Waerden numbers’, Graphs Combin. 2 (1986), 351–356.CrossRefGoogle Scholar
[7]Landman, B.M., ‘Ramsey functions related to the van der Waerden numbers’, Discrete Math. 102 (1992), 265–278.CrossRefGoogle Scholar
[8]Landman, B.M., ‘Ramsey functions associated with second order recurrences’, J. Combin. Math. Combin. Comput. 15 (1994), 119–127.Google Scholar
[9]Landman, B.M., ‘Ramsey functions for quasi-progressions’, Graphs Combin. (to appear).Google Scholar
[10]Nathanson, M.B., ‘Arithmetic progressions contained in sequences with bounded gaps’, Canadian Math. Bull. 23 (1980), 491–493.CrossRefGoogle Scholar
[11]Rabung, J.R., ‘On applications of van der Waerden's theorem’, Math. Magazine 48 (1975), 142–148.CrossRefGoogle Scholar
[12]Stevens, R.S. and Shantaram, R., ‘Computer generated van der Waerden partitions’, Math. Comput. 17 (1978), 635–636.CrossRefGoogle Scholar
[13]van der Waerden, B.L., ‘Beweis einer Baudetschen Vermutung’, Nieuw Arch. Wisk. 15 (1927), 212–216.Google Scholar