The exponential growth rate of Ramsey numbers

Every red-blue colouring of the edges of a large enough complete graph contains a red or a blue $K_k$. The smallest such size $R(k)$ grows exponentially, between roughly $\sqrt2^{\,k}$ and $4^k$. Erdős asked for the exact rate: does $R(k)^{1/k}$ converge, and to what? The first exponential improvement of the upper bound came only in 2023, 88 years after the classical bound.

Problem

Let $R(k)$ be the least $n$ such that every 2-colouring of the edges of the complete graph $K_n$ contains a monochromatic $K_k$. Determine

$$\lim_{k\to\infty} R(k)^{1/k},$$

and in particular prove that the limit exists.

The problem carries a $250 prize. Erdős offered $100 just for a proof that the limit exists, and $1000, later $10000, for a proof that it does not, calling that offer a joke because the limit "certainly exists".

Background

Erdős and Szekeres (1935) proved $R(k)<4^k$, and Erdős (1947) used a random colouring to show $R(k)>2^{k/2}$, one of the first applications of the probabilistic method. Together these give

$$\sqrt2\le\liminf_{k\to\infty}R(k)^{1/k}\le\limsup_{k\to\infty}R(k)^{1/k}\le 4.$$

Neither bound moved in the exponential scale for decades. Erdős wrote that perhaps the limit is $2$, "but we have no real evidence for this". His joke about an evil spirit demanding the value of $R(5)$ or $R(6)$, quoted on the source page, shows how hard even small cases are.

What is known

• Lower bound. $\liminf R(k)^{1/k}\ge\sqrt2$ is still the best; only the lower-order factor in Erdős's random bound has been improved.
• Upper bound. Campos, Griffiths, Morris and Sahasrabudhe (2023; Ann. of Math. 2026) proved $R(k)\le(4-\varepsilon)^k$ for a constant $\varepsilon>0$, giving $\limsup R(k)^{1/k}\le 4-\tfrac1{128}$. Gupta, Ndiaye, Norin and Wei (2024) shortened the argument and optimised it to $\limsup R(k)^{1/k}\le 3.7992\ldots$. Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe and Tiba (2024) gave a different, shorter proof of an exponential improvement that also extends to any number of colours.
• Whether the limit exists is unknown.

What would count as progress

• A proof that $\lim R(k)^{1/k}$ exists, even without its value.
• Any improvement of the lower bound $\sqrt2$ in the exponential scale, for example a colouring of $K_n$ with no monochromatic $K_k$ for $n=(\sqrt2+\delta)^k$, together with a proof.
• A further reduction of the upper constant $3.7992$, with an argument whose optimisation step can be checked numerically.
• A formal proof against the Lean statement in formal-conjectures.

References

1. P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2 (1935), 463–470. numdam.org
2. P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. doi:10.1090/S0002-9904-1947-08785-1
3. M. Campos, S. Griffiths, R. Morris and J. Sahasrabudhe, An exponential improvement for diagonal Ramsey, Ann. of Math. 203 (2026), 869–932. doi:10.4007/annals.2026.203.3.4
4. P. Gupta, N. Ndiaye, S. Norin and L. Wei, Optimizing the CGMS upper bound on Ramsey numbers (2024). arXiv:2407.19026
5. P. Balister, B. Bollobás, M. Campos, S. Griffiths, E. Hurley, R. Morris, J. Sahasrabudhe and M. Tiba, Upper bounds for multicolour Ramsey numbers (2024). arXiv:2410.17197

Source

Imported from Erdős Problems 77, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.