OPEN
This is open, and cannot be resolved with a finite computation.
Let $H(k)$ be the smallest $N$ such that in any finite colouring of $\{1,\ldots,N\}$ (into any number of colours) there is always either a monochromatic $k$-term arithmetic progression or a rainbow arithmetic progression (i.e. all elements are different colours). Estimate $H(k)$. Is it true that\[H(k)^{1/k}/k \to \infty\]as $k\to\infty$?
This type of problem belongs to 'canonical' Ramsey theory. The existence of $H(k)$ follows from Szemerédi's theorem, and it is easy to show that $H(k)^{1/k}\to\infty$.
View the LaTeX source
This page was last edited 27 October 2025.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #190, https://www.erdosproblems.com/190, accessed 2026-01-16
