{"id":"arxiv/2604.20588","url":"https://arxiv.org/abs/2604.20588","tags":["math.CO"],"score":0,"title":"A resolution of Erdős Problem #190 via Erdős-Lovász, BCT, and Baker-Harman-Pintz","domain":"math.CO","source":"arxiv","authors":["Ji Ho Bae"],"reviews":0,"subject":"math.CO","summary":"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 = Ω(k/\\log k)$ and $\\lim_{k\\to\\infty} H(k)^{1/k}/k = \\infty$, resolving the positive direction of the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-22","reactions":{}}