The order of long rainbow arithmetic progressions

2026/07/16 by Jesse Geneson
#math.CO #cs.DM

paper · pdf

Abstract

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

Related

• Long rainbow arithmetic progressions
• A note on long rainbow arithmetic progressions
• A Note On Rainbow 4-Term Arithmetic Progression
• Rainbow arithmetic progressions
• On sequences covering all rainbow k-progressions