Problem 165

Give an asymptotic formula for $R(3,k)$ .

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label. No asymptotic formula is proved; the search whose scope the Current assessment records found none, and no proof claim exists. The known bounds, each checked against its source, are

\Bigl(\frac12+o(1)\Bigr)\frac{k^2}{\log k}\ \le\ R(3,k)\ \le\ (1+o(1))\frac{k^2}{\log k},

the lower bound Hefty, Horn, King and Pfender's Theorem 1.2 (arXiv preprint, v3 of February 2026, no journal record), after Kim's $1/162$ (1995, refereed), Bohman and Keevash's and Fiz Pontiveros, Griffiths and Morris's $1/4$ (refereed, 2021 and 2020) and Campos, Jenssen, Michelen and Sahasrabudhe's $1/3$ (preprint, 2025); the upper bound Shearer's (1983, refereed; Theorem 1, the independence bound $\alpha\ge n(d\ln d-d+1)/(d-1)^2$ for triangle-free graphs of average degree $d$ , from which the Ramsey bound follows by an elementary step), sharpening Ajtai, Komlós and Szemerédi (1980, refereed; Theorem 3, $R(3,x)<100x^2/\ln x$ , from their Theorem 2, $\alpha(G)\ge0.01(n/t)\ln t$ for triangle-free graphs of average degree $t$ ). Campos, Jenssen, Michelen and Sahasrabudhe conjecture $c=1/2$ , and Hefty, Horn, King and Pfender restate the conjecture as their Conjecture 1.1 and support it. This is a bounded negative finding, not a certificate of openness.

HHKP25: Hefty, Z., Horn, P., King, D. and Pfender, F., Improving $R(3,k)$ in just two bites. arXiv:2510.19718 (v1 22 October 2025; v3 19 February 2026, 18 pages). Preprint; no journal record. Theorem 1.2, Theorem 1.3 and Conjecture 1.1, p. 2. Library home: Hefty et al. 2025.
CJMS25: Campos, M., Jenssen, M., Michelen, M. and Sahasrabudhe, J., A new lower bound for the Ramsey numbers $R(3,k)$ . arXiv:2505.13371 (v1 19 May 2025, 52 pages). Preprint; no journal record. Theorem 1.1 and display (1), pp. 1--2; Conjecture 1.2, p. 4. Library home: Campos et al. 2025.
BoKe21: Bohman, T. and Keevash, P., Dynamic concentration of the triangle-free process. Random Structures Algorithms 58 (2021), no. 2, 221--293, DOI 10.1002/rsa.20973; arXiv:1302.5963 (v2 4 September 2019, the version read, 75 pages; no file held; its pagination is not the journal's). Theorem 1.3, p. 2. Library home: Bohman and Keevash 2021.
PGM20: Fiz Pontiveros, G., Griffiths, S. and Morris, R., The triangle-free process and the Ramsey number $R(3,k)$ . Mem. Amer. Math. Soc. 263 (2020), no. 1274, v+125 pp., DOI 10.1090/memo/1274; arXiv:1302.6279 (v2 24 March 2018, 154 pages; its pagination is not the Memoir's). Theorem 1.2 and Conjecture 1.3, p. 4. Library home: Fizpontiveros 2020.
Ki95: Kim, J. H., The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$ . Random Structures Algorithms 7 (1995), no. 3, 173--207, DOI 10.1002/rsa.3240070302; cited by the pages of a 36-page typescript without the journal pagination. Theorem 1.1, typescript p. 1; the $R(3,t)$ bound, p. 2. Library home: Kim 1995.
Sh83: Shearer, J. B., A note on the independence number of triangle-free graphs. Discrete Math. 46 (1983), no. 1, 83--87, DOI 10.1016/0012-365X(83)90273-X. Theorem 1 and its proof, printed pp. 83--84; the paper prints the independence bound, not the Ramsey bound, and the step between them is recorded on the result page. Library home: Shearer 1983; paged at Shearer 1983, Theorem 1.
AKS80: Ajtai, M., Komlós, J. and Szemerédi, E., A note on Ramsey numbers. J. Combin. Theory Ser. A 29 (1980), no. 3, 354--360, DOI 10.1016/0097-3165(80)90030-8. Theorem 2, printed p. 355, and Theorem 3 with its proof, printed p. 358; the introduction's account of the earlier bounds, p. 354. Library home: Ajtai and Szemerédi 1980; paged at Ajtai and Szemerédi 1980, Theorem 2 and Ajtai and Szemerédi 1980, Theorem 3.
Mo26: Morris, R., Some recent results in Ramsey theory. Proc. ICM 2026, Vol. 2, 210--239, DOI 10.1137/25m1833369 (published online 13 July 2026); arXiv:2601.05221 (v1 8 January 2026, 37 pages). Theorem 1.2, p. 2. Expert attestation, not a review. Library home: Morris 2026.
GrYa68: Graver, J. E. and Yackel, J., Some graph theoretic results associated with Ramsey's theorem. J. Combinatorial Theory 4 (1968), 125--175; Proposition 9, printed p. 154: the 1968 upper bound $R(3,k)\ll k^2\log\log k/\log k$ in the paper's convention, one less than the usual Ramsey number. Library home: Proposition 9 (Graver and Yackel 1968).
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; item 6, printed pp. 98--99. Library home: Erdős 1971.
Er78: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Proc. Ninth Southeastern Conf. (Boca Raton, 1978), Congressus Numerantium XXI (1978), 29--40; display (4) and the sentence after it, printed p. 34. Library home: Erdős 1978.
Er81c: Erdős, P., Some new problems and results in graph theory and other branches of combinatorial mathematics. Lecture Notes in Math. 885 (1981), 9--17; item (5), printed p. 10, and the closing sentence of p. 11. Not a site key for this problem; the site's key for Problem 544. Library home: Erdős 1981.
Er61: Erdős, P., Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221--254. The passage behind the site's key is Part II, item 4, printed pp. 240--241: with $f(2,k,l)$ the two-class Ramsey function of p. 240, p. 241 reads "It would be interesting to determine $f(i,k,l)$ explicitely [sic], this seems very difficult even for $i=2$ " and "I can prove that (II.4.2) $f(2,3,k)>ck^2/(\log k)^2$ but could not decide whether $f(2,3,k)>c_2k^2$ is true". Library home: Erdős 1961.
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; display (13) and the asymptotic-formula sentence, printed p. 18. Library home: Erdős 1990.
Er93: Erdős, P., Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; Chapter II, displays (7) and (8) and the asymptotic-formula sentence, printed pp. 338--339. The site cites p. 339. 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; the $r_2(3,n)$ bounds and the asymptotic-formula sentence, printed p. 62. Library home: Erdős 1997; paged at Erdős 1997, Problem (pp. 62–63).
HHHKP26: Harris, S., Hefty, Z., Horn, P., King, D. and Pfender, F., A short proof that $R(3,k)=\Theta(k^2/\log k)$ . arXiv:2609.01782 (v1 1 September 2026, 7 pages). A lead, not filed in the library: Theorem 1.2 gives $R(3,k)\ge(\frac1{200}+o(1))k^2/\log k$ by a simplified two-bite construction and the note reproduces Shearer's proof of the upper bound.

Problem 165

Status

Proof claims

Discussion