Problem Statement
If $R(k)$ is the Ramsey number for $K_k$, the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$, then\[\frac{R(k)}{k2^{k/2}}\to \infty.\]
Categories:
Graph Theory Ramsey Theory
Progress
In [Er93] Erdő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ős and Szekeres [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ős gives\[R(k) \geq (1+o(1))\frac{1}{\sqrt{2}e}k2^{k/2},\]which Spencer [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)$.
Source: erdosproblems.com/1029 | Last verified: January 19, 2026