Mathematicians finally solved Erdős Problem #190 by determining the smallest integer needed to guarantee a specific pattern in a set of numbers.
April 23, 2026
Original Paper
A resolution of Erdős Problem #190 via Erdős-Lovász, BCT, and Baker-Harman-Pintz
arXiv · 2604.20588
The Takeaway
The resolution of this decades-old problem closes a major gap in the field of combinatorics. It defines the growth rate of H(k) using a combination of Erdős-Lovász and Baker-Harman-Pintz methods. Paul Erdős posed this challenge to the world over 50 years ago, and it has resisted all attempts until now. This definitive answer provides a new tool for understanding how order emerges in large, complex sets. It represents a significant victory for the branch of math that deals with monochromatic and rainbow progressions.
From the abstract
Let H(k) be the smallest N such that every finite coloring of [N] contains a monochromatic or rainbow k-term arithmetic progression. Erdős and Graham asked whether $H(k)^{1/k}/k \to \infty$ (Problem #190 of the Erdős Problems database). We prove that there is an absolute constant $k_0 \ge 2$ such that for all $k \ge k_0$, \[ H(k)^{1/k}/k \ge (1/e - \varepsilon(k)) \cdot k/\log k, \qquad \varepsilon(k) = O(k^{-0.475} \log k) \to 0 \text{ as } k \to \infty; \] in particular $H(k)^{1/k}/k = \Omega(