Campus Units

Computer Science, Electrical and Computer Engineering, Mathematics

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

2016

Journal or Book Title

Journal of Combinatorics

Volume

7

Issue

4

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 published as Butler, Steve, Craig Erickson, Leslie Hogben, Kirsten Hogenson, Lucas Kramer, Richard Kramer, Jephian C. H. Lin, Ryan R. Martin, Derrick Stolee, Nathan Warnberg, and Michael Young. "Rainbow Arithmetic Progressions." Journal of Combinatorics 7, no. 4 (2016): 595-626. 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