A resolution of Erdős Problem #190 via Erdős-Lovász, BCT, and Baker-Harman-Pintz

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 (k/\log k)$ and ${\lim }_{k\to \infty }H(k{)}^{1/k}/k=\infty$, resolving the positive direction of the Erdős-Graham question. The argument combines three standard ingredients -- the symmetric Lovász 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ős-Lovász had fixed $r$; the improvement here is that the $r^{k-1}$ base dominates once one allows the color count $r_0=\lfloor k/\log k\rfloor$ to grow with $k$. No matching upper bound on $H(k{)}^{1/k}/k$ is known.

10 pages