Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-06T19:44:41.105Z Has data issue: false hasContentIssue false
  • English
  • Français

Rainbow Arithmetic Progressions and Anti-Ramsey Results

Published online by Cambridge University Press:  03 December 2003

V Jungic ,
J Licht ,
M Mahdian ,
J Nesetril  and
R Radoicic
V Jungic*
Affiliation:
Department of Mathematics, Simon Fraser University, Burnaby, BC, V54 1S6, Canada
J Licht*
Affiliation:
William H. Hall High School, 975 North Main Street, West Hartford, CT 06117, USA
M Mahdian*
Affiliation:
Department of Mathematics, MIT, Cambridge, MA 02139, USA
J Nesetril*
Affiliation:
Department of Applied Mathematics, Charles University, Prague, Czech Republic
R Radoicic*
Affiliation:
Department of Mathematics, MIT, Cambridge, MA 02139, USA
*
(e-mail: vjungic@sfu.ca)
(e-mail: licht@mit.edu)
(e-mail: mahdian@math.mit.edu)
(e-mail: nesetril@kam.ms.mff.cuni.cz)
(e-mail: rados@math.mit.edu)
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.

The van der Waerden theorem in Ramsey theory states that, for every k and t and sufficiently large N, every k-colouring of [N] contains a monochromatic arithmetic progression of length t. Motivated by this result, Radoičić conjectured that every equinumerous 3-colouring of [3n] contains a 3-term rainbow arithmetic progression, i.e., an arithmetic progression whose terms are coloured with distinct colours. In this paper, we prove that every 3-colouring of the set of natural numbers for which each colour class has density more than 1/6, contains a 3-term rainbow arithmetic progression. We also prove similar results for colourings of . Finally, we give a general perspective on other anti-Ramsey-type problems that can be considered.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 12 , Issue 5-6: This issue contains volume twelve, parts five and six , November 2003 , pp. 599 - 620
Copyright
Copyright © Cambridge University Press 2003

Footnotes

†

Supported by the Czech Research Grant GA/V, CR/201/99/0242.

‡

Supported by Project LN00A056 of the Czech Ministry of Education.