Derrick Stolee - Iowa State University - Research Browser

Anti-Ramsey Numbers for $k$-Term Arithmetic Progressions Problem and Results Summary

In an additive group $G$, a $k$-term arithmetic progression ($k$-AP) is a set $X = \{ a + i\ell : i \in \{0,\dots,k-1\} \}$ for some pair $a, \ell \in G$. For a set $S \subseteq G$, an exact $r$-coloring of $S$ is a function $c : S \to [r]$ such that for every $j \in [r]$, $c^{-1}(j) \neq \varnothing$. We call the elements in $[r]$ colors and we wish to use as many colors as possible while avoiding rainbow $k$-APs ($k$-APs $X \subseteq S$ where every element of $X$ receives a distinct color).

Let $S \subseteq G$ be a subset of the group $G$ and define $\operatorname{aw}(S,k)$ be the minimum number $r$ such that every exact $r$-coloring of $S$ has at least one rainbow $k$-AP. When $S$ is finite, this number exists and is at most $|S|$. In [P16], we consider the two cases $S = [n] \subset {\mathbb Z} = G$ or $S = {\mathbb Z}_n \subset Z_n = G$. Our main results are summarized as follows:

• There exist constants $c_3, c_2$ such that $\log_3(n) + c_3 \leq \operatorname{aw}([n],3) \leq \log_2(n) + c_2$.
• $\operatorname{aw}({\mathbb Z}_{2^k},3) = 3$ for all $k$.
• $\operatorname{aw}([n],k) = n$ if and only if $k \geq \lceil (n+3)/2\rceil$.

We found the following open problem very interesting:

Conjecture. For all $n \geq 3$, $\operatorname{aw}([n+1],3) \geq \operatorname{aw}([n],3) - 1$.

It is worth discussing the previous work on this topic. Most previous work was focused on a different problem:

Question. Fix $r \geq k \geq 3$. Does there exist a value $\alpha_r$ has the property that if a coloring $c$ of the integers using $r$ colors such that every color class has density (strictly) more than $\alpha_r$ then there is a rainbow $k$-AP under $c$? What is the minimum such $\alpha_r$?

Research Papers
S. Butler, C. Erickson, L. Hogben, K. Hogenson, L. Kramer, R. L. Kramer, J. C.-H. Lin, R. R. Martin, D. Stolee, N. Warnberg, and M. Young, Rainbow arithmetic progressions submitted.
Web Version ArXiv Version
Software

Download rainbowaps.zip, unzip it, and type make to compile. The program rainbow.exe computes values of $\operatorname{aw}([n],k)$ and if given the argument k=3 it will compute only values $\operatorname{aw}([n],3)$. The program rainbow_zn.exe computes values of $\operatorname{aw}({\mathbb Z}_n,k)$ and if given the argument k=3 it will compute only values $\operatorname{aw}({\mathbb Z}_n,3)$.

Data
Support

This research was completed as part of the Discrete Mathematics Working Seminar at Iowa State University. Ryan Martin is partially supported by National Security Agency grant H98230-13-1-0226. Michael Young is partially supported by National Science Foundation grant DMS 0946431.

Related Work

J., Veselin, J. Licht (Fox), M. Mahdian, J. Nesetril, and R. Radoicic. Rainbow arithmetic progressions and anti-Ramsey results, Combinatorics, Probability & Computing 12:5-6 (2003) 599-620.

M. Axenovich and D. Fon-Der-Flaass, On rainbow arithmetic progressions, Electronic Journal of Combinatorics 11 (2004) #R1.

Rainbow Arithmetic Progressions I: Search Algorithm, Computational Combinatorics (Blog).

Rainbow Arithmetic Progressions II: The Collaboration, Computational Combinatorics (Blog).

Presentations
Rainbow Arithmetic Progressions. Combinatorics and Graph Theory Seminar (05/19), University of Colorado Denver.
Slides

(M. Young, presenter) Coloring the Integers with Rainbow Arithmetic Progressions Forty-Fifth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, March 6, 2014.
Slides

Derrick Stolee - Iowa State University - Research Browser