Computer Science, Electrical and Computer Engineering, Mathematics
Journal or Book Title
Journal of Combinatorics
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).
International Press of Boston, Inc.
Butler, Steve; Erickson, Craig; Hogben, Leslie; Hogenson, Kirsten; Kramer, Lucas; Kramer, Richard; Lin, Jephian C. H.; Martin, Ryan R.; Stolee, Derrick; Warnberg, Nathan; and Young, Michael, "Rainbow Arithmetic Progressions" (2016). Mathematics Publications. 58.