A resolution of Erdős Problem #190 via Erdős-Lovász, BCT, and Baker-Harman-Pintz
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913055145721856 |
|---|---|
| author | Bae, Ji Ho |
| author_facet | Bae, Ji Ho |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_20588 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A resolution of Erdős Problem #190 via Erdős-Lovász, BCT, and Baker-Harman-Pintz Bae, Ji Ho Combinatorics 05D10, 11B25, 05C65, 11N05 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 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. |
| title | A resolution of Erdős Problem #190 via Erdős-Lovász, BCT, and Baker-Harman-Pintz |
| topic | Combinatorics 05D10, 11B25, 05C65, 11N05 |
| url | https://arxiv.org/abs/2604.20588 |