Problem 1029

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.

Source: erdosproblems.com/1029

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. The best lower bound located is Spencer's Corollary 2 (J. Combinatorial Theory Ser. A 18 (1975)), $R(k)\ge k2^{k/2}[(\sqrt2/e)+o(1)]$ , a constant multiple of $k2^{k/2}$ ; the introduction of the 2023 diagonal upper-bound paper of Campos, Griffiths, Morris and Sahasrabudhe confirms that Erdős's 1947 bound "has only been improved by a factor of 2, by Spencer". No source proving a larger order or disproving divergence was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; the site cites p. 337 for the problem and the two offers. Chapter II, display (4), printed pp. 337--338. Erdős offers a prize for a proof of $(4)\quad \frac{r(n)}{n2^{n/2}}\to\infty$ "and 1000 dollars for a disproof of (4). This last offer is to some extent phoney: I am sure that (4) is true (but I have been wrong before)", in the survey's diagonal notation $r(n)$ for the page's $R(k)$ . Library home: Erdős 1993.
ErSz35: Erdős, P. and Szekeres, G., A combinatorial problem in geometry. Compos. Math. 2 (1935), 463--470; equation (3), p. 466. Library home: Erdős and Szekeres 1935.
Sp75: Spencer, Joel, Ramsey's theorem--a new lower bound. J. Combinatorial Theory Ser. A 18 (1975), no. 1, 108--115. Theorem 1 and Corollary 1, p. 109; Theorem 2 and Corollary 2, p. 110.
Er47: Erdős, P., Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53 (1947), 292--294; the probabilistic lower bound $R(k)>2^{k/2}$ . Not held; the record is taken from the reference lists of [Sp75] (its [1]) and [CGMS23] (its [11]), and the bound from Spencer's restatement.
CGMS23: Campos, M., Griffiths, S., Morris, R. and Sahasrabudhe, J., An exponential improvement for diagonal Ramsey. arXiv:2303.09521 (v1 16 March 2023; v2 4 August 2025); Ann. of Math. (2) 203 (2026), no. 3, DOI 10.4007/annals.2026.203.3.4. Context on upper bounds. Library home: Campos 2023.
MSX25: Ma, J., Shen, W. and Xie, S., An exponential improvement for Ramsey lower bounds. arXiv:2507.12926 (v1 17 July 2025; v2 26 April 2026). A lead from the discussion thread; not held.

Problem 1029

Status

Proof claims

Discussion