Logo
All Random Solved Random Open
SOLVED - $250
A set of integers $A$ is Ramsey $r$-complete if, whenever $A$ is $r$-coloured, all sufficiently large integers can be written as a monochromatic sum of elements of $A$. Prove any non-trivial bounds about the growth rate of such an $A$ for $r>2$.
A paper of Burr and Erdős [BuEr85] proves both upper and lower bounds for $r=2$, showing that there exists some $c>0$ such that it cannot be true that \[\lvert A\cap \{1,\ldots,N\}\rvert \leq c(\log N)^2\] for all large $N$, and also constructing a Ramsey $2$-complete $A$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert \ll (\log N)^3.\] Burr has shown that the sequence of $k$th powers is Ramsey $r$-complete for every $r,k\geq 1$.

Solved by Conlon, Fox, and Pham [CFP21], who constructed for every $r\geq 2$ an $r$-Ramsey complete $A$ such that for all large $N$ \[\lvert A\cap \{1,\ldots,N\}\rvert \ll r(\log N)^2,\] and showed that this is best possible, in that there exists some constant $c>0$ such that if $A\subset \mathbb{N}$ satisfies \[\lvert A\cap \{1,\ldots,N\}\rvert \leq cr(\log N)^2\] for all large $N$ then $A$ cannot be $r$-Ramsey complete.

See also [54].

Additional thanks to: Mehtaab Sawhney