Abstract
Let m ≥ 3 and k ≥ 1 be two given integers. A sub-k-coloring of [n] = {1, 2,..., n} is an assignment of colors to the numbers of [n] in which each color is used at most k times. Call an {Mathematical expression} a rainbow set if no two of its elements have the same color. The sub-k-Ramsey number sr(m, k) is defined as the minimum n such that every sub-k-coloring of [n] contains a rainbow arithmetic progression of m terms. We prove that Ω((k - 1)m2/log mk) ≤ sr(m, k) ≤ O((k - 1)m2 log mk) as m → ∞, and apply the same method to improve a previously known upper bound for a problem concerning mappings from [n] to [n] without fixed points.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 307-314 |
| Number of pages | 8 |
| Journal | Graphs and Combinatorics |
| Volume | 5 |
| Issue number | 1 |
| DOIs | |
| State | Published - Dec 1989 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
Fingerprint
Dive into the research topics of 'Sub-Ramsey numbers for arithmetic progressions'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver