Problem 986

For any fixed $s\geq 3$ ,

R(s,k) \gg \frac{k^{s-1}}{(\log k)^c}

for some constant $c=c(s)>0$ .

Source: erdosproblems.com/986

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED, the site's label (page last edited 21 June 2026). Bradač's Theorem 1.1 (arXiv:2605.28793v3, 16 June 2026) states that for any $s\ge3$ there is $c_s>0$ with $r(s,k)\ge c_sk^{s-1}/(\log k)^{2s-4}$ for all $k\ge2$ , so $c(s)=2s-4$ works. The status-defining source is an arXiv preprint, accepted by the site's curator, Thomas Bloom, who labels the problem PROVED and credits the lower bound to this paper as the resolution; no journal acceptance, other expert review or checked formalization of it was found, and the paper credits the step that raised the exponent from $s-2$ to $s-1$ to an internal model at OpenAI. The cases $s=3$ (Spencer 1977; the paper credits the bound to Erdős) and $s=4$ (Mattheus and Verstraete, Annals of Mathematics 2024) are refereed results and accepted partial claims. The frontmatter standing is derived from the claim pages: Bradač's result is an accepted full claim (claim page (Bradač, 2026)), its evidence the curator's review, and the two manuscripts of the OpenAI release of 24 September 2026, which claim the sharp logarithmic exponent $s-2+o(1)$ for every fixed $s\ge5$ , are an accepted partial claim (claim page (OpenAI, 2026)), its evidence the corpus's build and audit of the release's two Lean declarations.

Br26: Bradač, D., Off-diagonal Ramsey numbers. arXiv:2605.28793 (v1 27 May 2026, titled "Nearly tight exponents for off-diagonal Ramsey numbers", the title the site's reference carries; v2 11 June 2026; v3 16 June 2026, 19 pages). Preprint. Theorem 1.1, p. 2; the AI declaration, p. 4. Library home: Bradač 2026.
MaVe23: Mattheus, S. and Verstraete, J., The asymptotics of $r(4,t)$ . arXiv:2306.04007 (v5 20 February 2024); Ann. of Math. (2) 199 (2024), no. 2, DOI 10.4007/annals.2024.199.2.8. Theorem 1, p. 3 of the preprint. Library home: Mattheus and Verstraete 2023.
BoKe10: Bohman, T. and Keevash, P., The early evolution of the $H$ -free process. Invent. Math. 181 (2010), no. 2, 291--336; arXiv:0908.0429 (v1 4 August 2009). Theorem 1.2, p. 4 of the preprint. Library home: Bohman and Keevash 2010.
ErSz35: Erdős, P. and Szekeres, G., A combinatorial problem in geometry. Compos. Math. 2 (1935), 463--470; equation (3), p. 466, the upper bound. Library home: Erdős and Szekeres 1935.
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 6, printed p. 359 (PDF p. 6 of the publisher's open-archive scan). Library home: Ajtai and Szemerédi 1980; paged at Ajtai and Szemerédi 1980, Theorem 6.
LRZ01: Li, Y., Rousseau, C. C. and Zang, W., Asymptotic upper bounds for Ramsey functions. Graphs Combin. 17 (2001), 123--128, DOI 10.1007/s003730170060 (received 11 May 1998, final version 24 March 1999). Theorem 2, printed p. 124, and the concluding remarks, printed p. 127. Library home: Li, Rousseau and Zang 2001; paged at Li, Rousseau and Zang 2001, Theorem 2.
Sp77: Spencer, J., Asymptotic lower bounds for Ramsey functions. Discrete Math. 20 (1977), no. 1, 69--76, DOI 10.1016/0012-365X(77)90044-9. Theorem 2.1, printed p. 72 (PDF p. 4 of the publisher's open-archive scan), and Theorem 2.2, printed p. 74 (PDF p. 6); the site credits it with the case $s=3$ . Library home: Spencer 1977; paged at Spencer 1977, Theorem 2.1 and Spencer 1977, Theorem 2.2.
ChGr98: Chung, F. and Graham, R., Erdős on Graphs. His legacy of unsolved problems. A K Peters (1998); the site's reference for the 1947 attribution of the conjecture.
Er90b: Erdős, P., Problems and results on graphs and hypergraphs: similarities and differences. Mathematics of Ramsey theory (1990), 12--28; the site cites p. 18 and says the reference covers only $s=3,4$ . Library home: Erdős 1990 (p. 18: displays (13) and (14) state the cases $s=3$ and $s=4$ only).

Problem 986

Status

Proof claims

Discussion