Sub-Ramsey numbers for arithmetic progressions

Noga Alon, Yair Caro, Zsolt Tuza

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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 languageEnglish (US)
Pages (from-to)307-314
Number of pages8
JournalGraphs and Combinatorics
Issue number1
StatePublished - Dec 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Sub-Ramsey numbers for arithmetic progressions'. Together they form a unique fingerprint.

Cite this