Contents Online

# Journal of Combinatorics

## Volume 7 (2016)

### Number 4

### Rainbow arithmetic progressions

Pages: 595 – 626

DOI: http://dx.doi.org/10.4310/JOC.2016.v7.n4.a3

#### Authors

#### 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 $\mathrm{aw}([n], k)$ denotes the smallest number of colors with which the integers $\{1, \dotsc , n \}$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. We establish that $\mathrm{aw}([n], 3) = \Theta (\log n)$ and $\mathrm{aw} ([n], k) = n^{1-o(1)}$ for $k \geq 4$.

For positive integers $n$ and $k$, the expression $\mathrm{aw}(\mathbb{Z}_n, 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 $\mathrm{aw}(\mathbb{Z}_n, 3)$ behaves quite differently from $\mathrm{aw}([n], 3)$, depending on the divisibility of $n$. As shown in [Jungić et al., *Combin. Prob. Comput.,* 2003], $\mathrm{aw}(\mathbb{Z}_{2^m}, 3) = 3$ for any positive integer $m$. We establish $\mathrm{aw}(\mathbb{Z}_n, 3)$ can be computed from knowledge of $\mathrm{aw}(\mathbb{Z}_p, 3)$ for all of the prime factors $p$ of $n$. However, for $k \geq 4$, the behavior is similar to the previous case, that is, $\mathrm{aw}(\mathbb{Z}_n, k) = n^{1-o(1)}$.

#### Keywords

arithmetic progression, rainbow coloring, anti-Ramsey, Behrend construction