Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-23T22:11:17.439Z 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: [email protected])
(e-mail: [email protected])
(e-mail: [email protected])
(e-mail: [email protected])
(e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

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

‡

Supported by Project LN00A056 of the Czech Ministry of Education.