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. The limit in this question is closely related to the limit in
[627].
A famous quote of Erdő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ős I have found is in
[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.'
View the LaTeX source
This page was last edited 08 February 2026. View history
Additional thanks to: Alfaiz and Wouter van Doorn
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #77, https://www.erdosproblems.com/77, accessed 2026-04-11
