The order of long rainbow arithmetic progressions

Jesse Geneson

paper

The order of long rainbow arithmetic progressions

arXiv:2607.15116

Abstract

Let $T_{k}$ be the minimum positive integer $t$ such that, for every positive integer $n$ , every equinumerous $t$ -coloring of $[t n]$ contains a rainbow $k$ -term arithmetic progression. Jungić, Licht, Mahdian, Nešetřil and Radoičić conjectured that $T_{k} = Θ (k^{2})$ , while Conlon, Fox and Sudakov proved that $T_{k} = O (k^{2} lo g k)$ . We prove the matching lower bound $T_{k} = Ω (k^{2} lo g k)$ , and hence $T_{k} = Θ (k^{2} lo g k)$ .