OPEN
This is open, and cannot be resolved with a finite computation.
- $100
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.\]
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)$.
View the LaTeX source
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 #1029, https://www.erdosproblems.com/1029, accessed 2026-01-16
