Journal of Combinatorics

Volume 7 (2016)

Number 4

Rainbow arithmetic progressions

Pages: 595 – 626

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

Authors

Steve Butler (Dept. of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Craig Erickson (Dept. of Mathematics and Computer Science, Grand View University, Des Moines, Iowa, U.S.A.)

Leslie Hogben (Dept. of Mathematics, Iowa State University, Ames, Ia., U.S.A.; and American Institute of Mathematics, San Jose, California, U.S.A.)

Kirsten Hogenson (Dept. of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Lucas Kramer (Dept. of Mathematics, Bethel College, North Newton, Kansas, U.S.A.)

Richard L. Kramer (Dept. of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Jephian Chin-Hung Lin (Dept. of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Ryan R. Martin (Dept. of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Derrick Stolee (Depts. of Mathematics and Computer Science, Iowa State University, Ames, Ia., U.S.A.)

Nathan Warnberg (Dept. of Mathematics and Statistics, University of Wisconsin, La Crosse, Wisc., U.S.A.)

Michael Young (Dept. of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

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

Full Text (PDF format)

Published 16 August 2016