Problem 77

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 find the value of

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

Source: erdosproblems.com/77

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. Neither the existence nor the value of the limit is known. The lower end $\sqrt2$ is Erdős's 1947 bound $R(k)>2^{k/2}$ (as restated in Spencer's 1975 paper and in the introductions of [CGMS23], [BBCGHMST24] and [Mo26]); the upper end is the diagonal case of Theorem 1 of Gupta, Ndiaye, Norin and Wei, $R(k,k)\le(3.7992\ldots)^{k+o(k)}$ , an arXiv preprint (v2 of 29 August 2026) whose derivation declares AI assistance, while the refereed bounds are $R(k)\le(4-\varepsilon)^k$ with $\varepsilon=2^{-7}$ (Campos, Griffiths, Morris and Sahasrabudhe; Annals of Mathematics 2026) and the shorter proof of a $(4-c)^k$ bound by Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe and Tiba (J. Amer. Math. Soc. 2026). Erdős guessed "perhaps $c=2$ ?" (1988) with "no real evidence" (1993, p. 338). No source proving the existence of the limit, determining its value, or moving the lower end was found in the search whose scope the Current assessment records; a September 2026 preprint claiming a smaller upper base is recorded below as an unreviewed lead. This is a bounded negative finding, not a certificate of openness. The site lists a prize, Erdős's offer for the value of the limit.

CGMS23: Campos, M., Griffiths, S., Morris, R. and Sahasrabudhe, J., An exponential improvement for diagonal Ramsey. Ann. of Math. (2) 203 (2026), no. 3, 869--932, DOI 10.4007/annals.2026.203.3.4; arXiv:2303.09521 (v1 16 March 2023; v2 4 August 2025, the version cited). Theorem 1.1 and the two values of $\varepsilon$ , p. 2; Theorem 14.1, p. 48. Library home: Campos 2023.
GNNW24: Gupta, P., Ndiaye, N., Norin, S. and Wei, L., Optimizing the CGMS upper bound on Ramsey numbers. arXiv:2407.19026 (v1 26 July 2024; v2 29 August 2026, the version cited). Preprint. Theorem 1, p. 2; the diagonal bound, p. 3; the declaration, p. 3. Library home: Gupta 2024.
BBCGHMST24: Balister, P., Bollobás, B., Campos, M., Griffiths, S., Hurley, E., Morris, R., Sahasrabudhe, J. and Tiba, M., Upper bounds for multicolour Ramsey numbers. J. Amer. Math. Soc. 39 (2026), no. 3, 765--780, DOI 10.1090/jams/1069; arXiv:2410.17197 (v1 22 October 2024; v2 21 January 2026, read; no file held). Theorem 1.1, p. 2. Library home: Balister 2024.
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, J., Ramsey's theorem---a new lower bound. J. Combinatorial Theory Ser. A 18 (1975), 108--115; Theorem 1 and Corollary 1 (Erdős's bound), p. 109; Corollary 2, p. 110. Library home: Spencer 1975.
Er47: Erdős, P., the 1947 note with the probabilistic bound $R(k)>2^{k/2}$ , cited by [Sp75] as its reference [1] and by [CGMS23] as its [11]; not held, and its bibliographic data were not checked here.
Er88: Erdős, P., Problems and results in combinatorial analysis and graph theory. Discrete Math. 72 (1988), 81--92; Section 4, pp. 83--84. Library home: Erdős 1988.
Er69b: Erdős, P., Problems and results in chromatic graph theory. Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press (1969), 27--35; display (16), p. 31. Library home: Erdős 1969.
Er81c: Erdős, P., Some new problems and results in graph theory and other branches of combinatorial mathematics. Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math. 885 (1981), 9--17; items (3) and (4), p. 10. Library home: Erdős 1981.
Er95: Erdős, P., Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas 2 (1995), 165--186; Section II.9, p. 11 (the running-head number) of the 20-page author typescript. Library home: Erdős 1995.
Va99: Some of Paul's favorite problems, booklet for the conference "Paul Erdős and his mathematics", Budapest, July 1999; item 3.50. Library home: Various 1999.
Er90b: Erdős, P., Problems and results on graphs and hypergraphs: similarities and differences. Mathematics of Ramsey theory, Algorithms Combin. 5, Springer (1990), 12--28; the site cites p. 17, where Section 3 states the bounds and the two prize offers. Library home: Erdős 1990.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42. A site key (card); its passage for this problem is located on the card at Part V, display (1), p. 9 of the copy the card describes (the prize offers with the bounds $2^{1/2}$ and $4$ ).
Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97--109; the site cites p. 99 (card); its passage for this problem is located on the card at its item for this problem (the request on p. 99 to prove that $\lim f(n,n)^{1/n}$ exists, with the bounds (3)--(4)).
Er61: Erdős, P., Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221--254. A site key (card); the passage is Part II, item 4, printed pp. 240--241, where the print spells the name "RAMSAY": after (II.4.1) $2^{k/2}<f(2,k,k)\le\binom{2k-2}{k-1}$ for the two-class Ramsey function $f(2,k,l)$ , p. 241 reads "I have not even be [sic] able to prove that $\lim_{i=\infty} f(2,k,k)^{1/k}$ [sic] exists".
Er93: Erdős, P., Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; Chapter II, display (5) with the two prize offers, the "no real evidence" sentence and the evil-spirit joke, printed p. 338 (the displays as the library card records them). The site cites p. 338. Library home: Erdős 1993.
Er97c: Erdős, P., Some of my favorite problems and results. The mathematics of Paul Erdős, I, Algorithms Combin. 13, Springer (1997), 47--67; display (4.2) and the two prize offers, printed p. 62. Library home: Erdős 1997; paged at Erdős 1997, Display (4.2).
Er97d: Erdős, P., Some recent problems and results in graph theory. Discrete Math. 164 (1997), 81--85; item 6, p. 83. Library home: Erdős 1997.
Mo26: Morris, R., Some recent results in Ramsey theory. Proceedings of the International Congress of Mathematicians 2026, Vol. 2, 210--239, DOI 10.1137/25m1833369; arXiv:2601.05221v1 (8 January 2026). Theorem 1.1 and display (1), p. 1. Library home: Morris 2026.
Wi24: Wigderson, Y., Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe]. Séminaire Bourbaki, exposé 1230 (November 2024); arXiv:2411.09321 (v2 20 December 2024); Astérisque (2026), DOI 10.24033/ast.1255. Abstract and Crossref record only; not held.
Pa25: Paulson, L. C., Formalising New Mathematics in Isabelle: Diagonal Ramsey. arXiv:2501.10852 (18 January 2025). Abstract only; not held.
LuWa26: Lu, Z. and Wang, S., Retained-Set Descent for Diagonal Ramsey Numbers. arXiv:2609.14525 (v1 13 September 2026). Abstract only; a preprint claim recorded as a lead below; not held.

Problem 77

Status

Proof claims

Discussion