The order of long rainbow arithmetic progressions
Discrete Mathematics
Summary
The authors studied a problem about coloring numbers in a sequence so that certain patterns, called rainbow arithmetic progressions, always appear. Previous researchers guessed the minimum number of colors needed, called T_k, grew roughly like k squared. Others showed it grows no faster than k squared times log k. The authors proved that this faster growth is actually necessary, confirming that T_k grows on the order of k squared times log k. This settles the question about how the minimum number of colors behaves for these patterns.
Authors
Jesse Geneson
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^2)$, while Conlon, Fox and Sudakov proved that $T_k=O(k^2\log k)$. We prove the matching lower bound $T_k=Ω(k^2\log k)$, and hence $T_k=Θ(k^2\log k)$.