Long rainbow arithmetic progressions

Abstract

Define $T_k$ as the minimal $t\in \mathbb{N}$ for which there is a rainbow arithmetic progression of length $k$ in every equinumerous $t$-coloring of $[tn]$ for all $n\in \mathbb{N}$. Jungić, Licht (Fox), Mahdian, Nesetril and Radoicić proved that $\lfloor \frac{k^2}{4}\rfloor \le T_k$. We almost close the gap between the upper and lower bounds by proving that $T_k\le k^2{e}^{(\ln \ln k{)}^2(1+o(1))}$. Conlon, Fox and Sudakov have independently shown a stronger statement that $T_k=O(k^2\log k)$.

Minor revisions, to appear in Journal of Combinatorics