The order of long rainbow arithmetic progressions

Jesse Geneson

combinatorics

The order of long rainbow arithmetic progressions

arXiv:2607.15116

summary

The paper determines the asymptotic growth of the minimum number of colors needed so that any equinumerous coloring of a large integer interval contains a rainbow arithmetic progression of length k, proving it is Θ(k² log k).

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} = I^ (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} = I^c ◯ (k^{2} lo g k)$ , and hence $T_{k} = I^ (k^{2} lo g k)$ .

Topics & keywords

#rainbow arithmetic progressions #colorings #extremal combinatorics #asymptotic bounds #arithmetic progressionsT_krainbow k-term progressionequinumerous coloringlower boundΘ(k^2 log k)