Rainbow Arithmetic Progressions

Date
2016-01-01
Authors
Butler, Steve
Erickson, Craig
Hogben, Leslie
Hogenson, Kirsten
Hogben, Leslie
Kramer, Lucas
Kramer, Richard
Lin, Jephian
Martin, Ryan
Stolee, Derrick
Warnberg, Nathan
Young, Michael
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Mathematics
Organizational Unit
Journal Issue
Series
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).

Description
<p>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." <em>Journal of Combinatorics </em>7, no. 4 (2016): 595-626. DOI: <a href="https://doi.org/10.4310/JOC.2016.v7.n4.a3" target="_blank">10.4310/JOC.2016.v7.n4.a3</a>. Posted with permission.</p>
Keywords
arithmetic progression, rainbow coloring, anti-Ramsey, Behrend construction
Citation
Collections