In \cite{Er93} Erd\H{o}s offers \$100 for a proof of this and \$1000 for a disproof, but says 'this last offer is to some extent phoney: I am sure that [this] is true (but I have been wrong before).'

Erd\H{o}s and Szekeres \cite{ErSz35} proved\[k2^{k/2} \ll R(k) \leq \binom{2k-1}{k-1}.\]One of the first applications of the probabilistic method pioneered by Erd\H{o}s gives\[R(k) \geq (1+o(1))\frac{1}{\sqrt{2}e}k2^{k/2},\]which Spencer \cite{Sp75} improved by a factor of $2$ to\[R(k) \geq (1+o(1))\frac{\sqrt{2}}{e}k2^{k/2}.\]See also [77] for a more general problem concerning $\lim R(k)^{1/k}$, and discussion of upper bounds for $R(k)$.


References


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

[ErSz35] Erd\H{o}s, P. and Szekeres, G., A combinatorial problem in geometry. Compos. Math. (1935), 463-470.

[Sp75] Spencer, Joel, Ramsey's theorem---a new lower bound. J. Combinatorial Theory Ser. A (1975), 108--115.