A resolution of Erd\H{o}s Problem #190 via Erd\H{o}s-Lov\'asz, BCT, and Baker-Harman-Pintz

Let H(k) be the smallest N such that every finite coloring of [N] contains a monochromatic or rainbow k-term arithmetic progression. Erd\H{o}s and Graham asked whether $H(k{)}^{1\mathrm{/}k}\mathrm{/}k\to \mathrm{\infty }$ (Problem #190 of the Erd\H{o}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\mathrm{/}k}\mathrm{/}k\ge (1\mathrm{/}e-\epsilon (k))\cdot k\mathrm{/}\log k,\epsilon (k)=O(k^{-0.475}\log k)\to 0\text{ as }k\to \mathrm{\infty };$$ in particular $H(k{)}^{1\mathrm{/}k}\mathrm{/}k=\mathrm{\Omega }(k\mathrm{/}\log k)$ and ${\lim }_{k\to \mathrm{\infty }}H(k{)}^{1\mathrm{/}k}\mathrm{/}k=\mathrm{\infty }$, resolving the positive direction of the Erd\H{o}s-Graham question. The argument combines three standard ingredients – the symmetric Lov'asz Local Lemma applied to the k-AP hypergraph on $[N]$, the restricted form of the Blankenship-Cummings-Taranchuk recurrence, and the Baker-Harman-Pintz prime-gap theorem – together with the pigeonhole reduction $H(k)\ge W(k-1,k)$, and uses BHP as the only analytic black box. Previous applications of Erd\H{o}s-Lov'asz had fixed $r$; the improvement here is that the $r^{k-1}$ base dominates once one allows the color count $r_0=\lfloor k\mathrm{/}\log k\rfloor$ to grow with $k$. No matching upper bound on $H(k{)}^{1\mathrm{/}k}\mathrm{/}k$ is known.