Erdős Problem #190
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: additive combinatorics, arithmetic progressions.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Colour the integers \(1,\ldots,N\) using any finite number of colours. A \(k\) term arithmetic progression is monochromatic if all its members share one colour and rainbow if every member has a different colour.
Define \(H(k)\) as the smallest \(N\) forcing at least one of these two patterns in every such colouring. Erdős and Graham asked for the growth of this canonical Ramsey threshold, and in particular whether
Unlike ordinary van der Waerden numbers, the number of colours here is not fixed in advance; requiring either a monochromatic or rainbow pattern is essential for a finite universal threshold.
A small example
For \(k=2\), a pair of different integers is always either monochromatic or rainbow, so \(H(2)=2\). For \(k=3\), a three-term progression with colours red, red, blue is neither monochromatic nor rainbow. One must check every nonconstant progression, not merely whether a colour occurs twice.
The quantifier “any finite colouring” permits arbitrarily many colours depending on \(N\). A proof of a bound for just two colours cannot establish the canonical threshold.
What is known
SOLVED for the stated divergence. Fox and Hunter, Three-color van der Waerden numbers grow super-exponentially (2026), derived the strong lower estimate
It implies \(H(k)^{1/k}/k\to\infty\) directly. Bae's independent 2026 paper gave the earlier lower estimate \(H(k)\ge k^{(2-o(1))k}\), which would imply the same divergence. Hunter's preceding recurrence already implied that \(H(k)^{1/k}\to\infty\), a weaker conclusion than division by an additional factor of \(k\).
The maintained Erdős #190, updated June 2026, labels the original question SOLVED. The full exact asymptotic behaviour of \(H(k)\) remains a separate problem; the stated limit does not give matching upper and lower bounds.
GCL's current state
The pinned and maintained classification is SOLVED. Original issue: #1459. The June 2026 manuscript's exponent and implication were checked as source claims, but its proof and any externally reported formalization have not been independently replayed.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded successor enumerates all set partitions (colourings up to renaming) of \([1,N]\) for \(N\le8\) and checks every \(k=2,3\) progression for monochromatic or rainbow patterns. Acceptance: \(H(2)=2\) and a second independent predicate checker agrees. Separately formalize the elementary implication from the 2026 lower bound to the divergence of \(H(k)^{1/k}/k\); stop before asserting any new asymptotic constant.
Sources and claim boundaries
- Fox–Hunter, arXiv:2606.02541, primary 2026 lower bound.
- Bae, arXiv:2604.20588, independent earlier bound.
- Maintained Erdős #190; GCL issue #1459.
No new canonical Ramsey theorem, independent formal-proof certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1459 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.