Rainbow Arithmetic Progressions
Is Version Of
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).
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.