Campus Units

Computer Science, Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

2016

Journal or Book Title

Journal of Combinatorics

Volume

7

First Page

595

Last Page

626

DOI

10.4310/JOC.2016.v7.n4.a3

Abstract

In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers n and k, the expression aw([n]; k) denotes the smallest number of colors with which the integers f1; : : : ; ng can be colored and still guarantee there is a rainbow arithmetic progression of length k. We establish that aw([n]; 3) = (log n) and aw([n]; k) = n1o(1) for k 4. For positive integers n and k, the expression aw(Zn; k) denotes the smallest number of colors with which elements of the cyclic group of order n can be colored and still guarantee there is a rainbow arithmetic progression of length k. In this setting, arithmetic progressions can \wrap around," and aw(Zn; 3) behaves quite differently from aw([n]; 3), depending on the divisibility of n. As shown in [Jungic et al., Combin. Probab. Comput., 2003], aw(Z2m; 3) = 3 for any positive integer m. We establish that aw(Zn; 3) can be computed from knowledge of aw(Zp; 3) for all of the prime factors p of n. However, for k 4, the behavior is similar to the previous case, that is, aw(Zn; k) = n1o(1).

Comments

This is a manuscript of an article from the Journal of Combinatorics 7 (2016): 595, doi: 10.4310/JOC.2016.v7.n4.a3. Posted with permission.

Copyright Owner

International Press of Boston, Inc.

Language

en

File Format

application/pdf

Published Version

Share

COinS