A resolution of Erdős Problem #190 via Erdős-Lovász, 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ő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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.20588
curl -X POST /api/v1/records/arxiv/2604.20588/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.20588/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'