Logo
All Random Solved Random Open
OPEN - $250
Find the value of $\lim_{k\to \infty}R(k)^{1/k}$.
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'. 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].

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