Erdős offered \$100 for just a proof of the existence of this constant, without determining its value. He also offered \$1000 for a proof that the limit does not exist, but says 'this is really a joke as [it] certainly exists'. (In [Er88] he raises this prize to \$10000). Erdős proved\[\sqrt{2}\leq \liminf_{k\to \infty}R(k)^{1/k}\leq \limsup_{k\to \infty}R(k)^{1/k}\leq 4.\]The upper bound has been improved to $4-\tfrac{1}{128}$ by Campos, Griffiths, Morris, and Sahasrabudhe [CGMS23]. This was improved to $3.7992\cdots$ by Gupta, Ndiaye, Norin, and Wei [GNNW24].

A shorter and simpler proof of an upper bound of the strength $4-c$ for some constant $c>0$ (and a generalisation to the case of more than two colours) was given by Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba [BBCGHMST24].

In [Er93] Erdős writes 'I have no idea what the value of $\lim R(k)^{1/k}$ should be, perhaps it is $2$ but we have no real evidence for this.'

This problem is #3 in Ramsey Theory in the graphs problem collection.

See also [1029] for a problem concerning a lower bound for $R(k)$ and discussion of lower bounds in general.

View the LaTeX source

This page was last edited 08 December 2025.