The Ramsey property for collections of sequences not containing all arithmetic progressions
- Tom C. Brown(corresponding author),
- Bruce M. Landman
- Simon Fraser University,
- University of North Carolina at Greensboro
Abstract
A family ℬ of sequences has the Ramsey property if for every positive integer k, there exists a least positive integer fℬ(k) such that for every 2-coloring of {1, 2, . . . , fℬ(k)} there is a monochromatic k-term member of ℬ. For fixed integers m > 1 and 0 ≤ q < m, let ℬq(m) be the collection of those increasing sequences of positive integers {x1 , . . . , xk} such that xi+1 - xi = q(mod m) for 1 ≤ i ≤ k - 1. For t a fixed positive integer, denote by script A signt the collection of those arithmetic progressions having constant difference t. Landman and Long showed that for all m ≥ 2 and 1 ≤ q < m, ℬq(m) does not have the Ramsey property, while ℬq(m) ∪ script A signm does. We extend these results to various finite unions of ℬq(m)'s and script A signt's. We show that for all m ≥ 2, ∪q=1m-1 ℬq(m) does not have the Ramsey property. We give necessary and sufficient conditions for collections of the form ℬq(m) ∪ (∪t ∈ T script A signt) to have the Ramsey property. We determine when collections of the form ℬa(m1) ∪ ℬb(m2) have the Ramsey property. We extend this to the study of arbitrary finite unions of ℬq(m)'s. In all cases considered for which ℬ has the Ramsey property, upper bounds are given for fℬ.
Publication Information
Output type
Original language
English (US)Pages from-to (Number of pages)
Pages 149-161 (13 pages)Journal (Volume, Issue Number)
Graphs and Combinatorics (Volume 12, Issue 2)Publication milestones
- Published - 1996
Publication status
ISSN
0911-0119Publication IDs
- Scopus: 10044253858
