Erd\H{o}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 \cite{Er88} he raises this prize to \$10000). Erd\H{o}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 \cite{CGMS23}. This was improved to $3.7992\cdots$ by Gupta, Ndiaye, Norin, and Wei \cite{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\'{a}s, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba \cite{BBCGHMST24}.

In \cite{Er93} Erd\H{o}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.

A famous quote of Erd\H{o}s concerns the difficulty of finding exact values for $R(k)$. This is often repeated in the words of Spencer, who phrased it as an alien attacking race. The earliest such quote in a paper of Erd\H{o}s I have found is in \cite{Er93}, where he writes:

'Sometime ago, I made the following joke. If an evil spirit would appear and say "unless you give me the value of $R(5)$ within a year, I will exterminate humanity", then our best bet would be perhaps to get all our computers working on $R(5)$ and we probably would get its value in a year.

If he would ask for $R(6)$, the best strategy probably would be to destroy it before it can destroy us. If we would be so clever that we could give the answer by mathematics, we would just tell him: "if you try to do something you will see what will happent to you...". I think we are strong enugh now and the only evil spirit we have to feel is the one which is in ourselves (quoting somebody: I have seen the enemy and them are us). Now enough of the idle talk and back to Mathematics.'


References


[BBCGHMST24] Balister, P. and Bollob\'{a}s, B. and Campos, M. and Griffiths, S. and Hurley, E.
and Morris, R. and Sahasrabudhe, J. and Tiba, M., Upper bounds for multicolour Ramsey numbers. arXiv:2410.17197 (2024).

[CGMS23] Campos, Marcelo and Griffiths, Simon and Morris, Robert and Sahasrabudhe, Julian, An exponential improvement for diagonal Ramsey. arXiv:2303.09521 (2023).

[Er88] Erd\H{o}s, P, Problems and results in combinatorial analysis and graph theory. Discrete Math. (1988), 81-92.

[Er93] Erd\H{o}s, Paul, Some of my favorite solved and unsolved problems in graph
theory. Quaestiones Math. (1993), 333-350.

[GNNW24] Gupta, P. and Ndiaye, N. and Norin, S. and Wei, L., Optimizing the CGMS upper bound on Ramsey numbers. arXiv:2407.19026 (2024).