Problem 1014

Let $R(k,l)$ be the Ramsey number, so the minimal $n$ such that every graph on at least $n$ vertices contains either a $K_k$ or an independent set on $l$ vertices.

Prove, for fixed $k\geq 3$ , that

\lim_{l\to \infty}\frac{R(k,l+1)}{R(k,l)}=1.

Source: erdosproblems.com/1014

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN). The status-defining source is Theorem 1 of a three-page manuscript, On the ratio of $R(k,\ell)$ and $R(k,\ell+1)$ , hosted by OpenAI (retrieved; its PDF metadata is dated 22 April 2026), which proves $\lim_{\ell\to\infty}R(k,\ell+1)/R(k,\ell)=1$ for every fixed integer $k\ge2$ by dependent random choice on a critical graph. Its author is OpenAI; the manuscript's abstract attributes the proof to an internal model at OpenAI. The site accepted it as the resolution on 24 April 2026 with the label PROVED (LEAN). This is a source-supported solution accepted by the site, distinct from a claim of journal refereeing: no refereed publication, no arXiv version and no independent expert review of the manuscript was found on 2026-09-18. Two external Lean developments prove the theorem for their own definitions of the Ramsey number at pinned revisions; they are not built or independently audited here, and no local kernel credit is claimed. The claim page OpenAI 2026 records the manuscript, its two external formalizations and the site's acceptance as an accepted full result, and the frontmatter standing derives from it: accepted on the one evidence kind the curator's crediting of the manuscript supplies (reviewed), with no refereed version and no independent review of the whole argument.

OpenAI26: OpenAI, On the ratio of $R(k,\ell)$ and $R(k,\ell+1)$ . Three-page manuscript, https://cdn.openai.com/pdf/6dc7175d-d9e7-4b8d-96b8-48fe5798cd5b/Ramsey.pdf, retrieved (HTTP 200); undated in its text, PDF metadata 22 April 2026; no author names beyond the abstract's "The proof is due to an internal model at OpenAI." Theorem 1 and Remark 1, p. 1; proof, pp. 2--3. Library home: OpenAI 2026.
Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press, London (1971), 97--109; item 6, printed pp. 98--99. Library home: Erdős 1971.
ErSz35: Erdős, P. and Szekeres, G., A combinatorial problem in geometry. Compos. Math. 2 (1935), 463--470; the bound $R(k,\ell)\le\binom{k+\ell-2}{k-1}$ is the manuscript's Lemma 1. Library home: equation (3).
FoSu11: Fox, J. and Sudakov, B., Dependent random choice. Random Structures Algorithms 38 (2011), 68--99; its Lemma 2.1 is the manuscript's Lemma 3. Not held; cited as the manuscript cites it.
BoKe10: Bohman, T. and Keevash, P., The early evolution of the $H$ -free process. Invent. Math. 181 (2010), 291--336; the manuscript's context for the general lower bounds. Library home: Bohman and Keevash 2010 (not consumed here).
MaVe23: Mattheus, S. and Verstraete, J., The asymptotics of $r(4,t)$ . Ann. of Math. (2) 199 (2024), 919--941; the manuscript's context for $R(4,\ell)=\ell^{3+o(1)}$ . Library home: Mattheus and Verstraete 2023 (not consumed here).
Sp77: Spencer, J., Asymptotic lower bounds for Ramsey functions. Discrete Math. 20 (1977), 69--76; Theorem 2.2, printed p. 74, the lower bound $R(k,t)\ge c(t/\ln t)^{(k+1)/2}[1-o(1)]$ for fixed $k\ge3$ . Library home: Spencer 1977, Theorem 2.2.
Br26: Bradač, D., Off-diagonal Ramsey numbers. arXiv:2605.28793v3 (16 June 2026); Theorem 1.1, p. 2, the lower bound $r(s,k)\ge c_sk^{s-1}/(\log k)^{2s-4}$ for fixed $s\ge3$ . Library home: Bradač 2026, Theorem 1.1.

Problem 1014

Status

Proof claims

Discussion