Journal of Combinatorics

Volume 12 (2021)

Number 3

Long rainbow arithmetic progressions

Pages: 547 – 550

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n3.a6

Authors

József Balogh (Department of Mathematical Sciences, University of Illinois at Urbana-Champaign, Urbana, Il., U.S.A.; and Moscow Institute of Physics and Technology, Russian Federation)

William Linz (Department of Mathematical Sciences, University of Illinois at Urbana-Champaign, Urbana, Il., U.S.A.)

Letícia Mattos (Instituto Nacional de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, Brazil)

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, Nešetřil and Radoičić proved that $\lfloor \frac{k^2}{4} \rfloor \leq T_k \leq k(k-1)^2 / 2$. We almost close the gap between the upper and lower bounds by proving that $T_k \leq 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 \operatorname{log} k)$.

Keywords

rainbow $k$-AP, equinumerous $t$-coloring

2010 Mathematics Subject Classification

05D99

Full Text (PDF format)

The first-named author was partially supported by NSF Grant DMS-1500121 and DMS-1764123, Arnold O. Beckman Research Award (UIUC Campus Research Board RB 18132) and the Langan Scholar Fund (UIUC).

The third-named author was partially supported by CAPES.

Received 24 July 2019

Accepted 15 September 2020

Published 8 November 2021