Problem #188: What is the smallest $k$ such that $\mathbb{R}^2$ can be...

---

Progress

Erdős, Graham, Montgomery, Rothschild, Spencer, and Straus [EGMRSS75] proved $k\geq 5$. Tsaturian [Ts17] improved this to $k\geq 6$. Erdős and Graham claim that $k\leq 10000000$ ('more or less'), but give no proof.

Erdős and Graham asked this with just any $k$-term arithmetic progression in blue (not necessarily with distance $1$), but Alon has pointed out that in fact no such $k$ exists: in any red/blue colouring of the integer points on a line either there are two red points distance $1$ apart, or else the set of blue points and the same set shifted by $1$ cover all integers, and hence by van der Waerden's theorem there are arbitrarily long blue arithmetic progressions.

It seems most likely, from context, that Erdős and Graham intended to restrict the blue arithmetic progression to have distance $1$ (although they do not write this restriction in their papers).