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

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

- rainbowapdata.zip contains complete output files for runs of the above software.
- rainbowaps_all_values.txt contains all output information from the computational experiments.
- For information regarding computations of $\operatorname{aw}([n],k)$, see
- rainbowaps_k3_examples.txt (Extremal examples for $k = 3$)
- rainbowaps_k3_times.txt (Computation times for $k=3$)
- rainbowaps_allk_examples.txt (Extremal examples for all $k$)
- rainbowaps_allk_times.txt (Computation times for all $k$).

- For information regarding computations of $\operatorname{aw}({\mathbb Z}_n,k)$, see
- rainbowaps_zn_k3_examples.txt (Extremal examples for $k = 3$)
- rainbowaps_zn_k3_times.txt (Computation times for $k=3$)
- rainbowaps_zn_allk_examples.txt (Extremal examples for all $k$)
- rainbowaps_zn_allk_times.txt (Computation times for all $k$).

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

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