---

Claim. There is a constant $c$ such that some 2-coloring of the integers has no monochromatic arithmetic progression of common difference $d$ with more than $cd$ terms, for every $d$; so the best $f$ of Problem 187 satisfies $f(d)<cd$. Erdős states the bound in Section 2 (printed p. 121) of P. Erdős, Problems and results on combinatorial number theory, A Survey of Combinatorial Theory (Fort Collins, 1971), North-Holland (1973), 117--138, and sketches the coloring: for a quadratic irrational $\alpha$, put $n$ in the first class when the fractional part of $n\alpha$ is below $\frac12$ and in the second otherwise. Along a progression of difference $d$ the fractional parts advance by $\{d\alpha\}$, which the inequality $|\alpha-p/q|>c_1/q^2$ keeps at least $c_1/d$ away from every integer, so a monochromatic run has length $O(d)$. The passage is recorded on the chapter's library card. Erdős repeats the bound in his 1976 and 1980 surveys and, with Graham, in their 1979 and 1980 surveys, as the problem page records.

Covers. The upper bound $f(d)=O(d)$ on the best $f$ alone, superseded by Beck's bound $(1+o(1))\log_2d$. Not covered: any lower bound, and the determination of the best $f$.

Depends on. Nothing in this wiki; the claim rests on the cited chapter.

Standing. The chapter appears in a proceedings volume, and no evidence that the volume was refereed is on record, so no refereed evidence is listed. The site's curator credits the bound to Erdős in the problem's commentary, but the site labels the problem OPEN, so that credit is not acceptance. The claim stays claimed; the year is the chapter's only date, so the page is named by the first day of 1973. The corpus records no check of the argument beyond the sketch above.