Growth of consecutive diagonal Ramsey numbers: is $R(n+1)/R(n)\geq 1+c$? (Erdős #812)
Statement
Let $R(n)=R(n,n)$ be the diagonal Ramsey number: the least $N$ such that every red/blue colouring of the edges of the complete graph $K_N$ contains a monochromatic $K_n$. Two questions about how fast $R(n)$ grows between consecutive values. (i) Does there exist a constant $c>0$ with $$\frac{R(n+1)}{R(n)}\geq 1+c$$ for all large $n$? (ii) Does the gap satisfy $$R(n+1)-R(n)\gg n^2\,?$$
Acceptance. FULLY RESOLVES: a complete proof of, or disproof of, either the multiplicative claim (there is $c>0$ with $R(n+1)/R(n)\geq 1+c$ for all large $n$) or the additive claim ($R(n+1)-R(n)\gg n^2$); a machine-checkable proof (Lean/Coq) is preferred, otherwise a full rigorous proof with all constants and thresholds. ADVANCES: any rigorous improvement to the stated gap bounds — for instance a super-linear lower bound on the one-step gap $R(n+1)-R(n)$ beyond the current $4n-8$, or a sharpening of the two-step $R(n+2)-R(n)\gg n^{2-o(1)}$ toward the conjectured order — with a complete proof; or a proof of the ratio bound conditional on a clearly-stated hypothesis about the growth of $R(n)$. A finite table of Ramsey values can never settle an asymptotic claim and does not qualify. Deliver the proof file or written proof with explicit bounds.
Background
Posed by Erdős [Er91]. Best known: Burr, Erdős, Faudree, and Schelp [BEFS89] proved the linear gap bound $R(n+1)-R(n)\geq 4n-8$ for all $n\geq 2$. The Ramsey lower-bound machinery behind Erdős #165 (erdosproblems.com/165) yields $R(n+2)-R(n)\gg n^{2-o(1)}$ for the two-step gap — tantalisingly close to the conjectured order $n^2$ but not settling the one-step questions (i) and (ii). Companion problems on Bloom's tracker: Erdős #1030 (erdosproblems.com/1030) asks the analogous ratio question for the near-diagonal step $R(k+1,k)/R(k,k)$, and Erdős #1029 (erdosproblems.com/1029) asks whether $R(n)/(n\,2^{n/2})\to\infty$. A formalised (Lean) statement of this problem exists. Related OEIS sequence: A059442 (array of Ramsey numbers $R(n,k)$). Listed as open on erdosproblems.com/812 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). Attacker's tool: this is purely proof-shaped — diagonal Ramsey numbers are known exactly only through $R(4)=18$, with $R(5)$ still open — so no computation touches the asymptotic; progress means a new analytic argument, most plausibly refining the Burr–Erdős–Faudree–Schelp gap bound or the probabilistic/constructive bounds behind #165.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #812 (T. F. Bloom) | website |
| REF-02 | OEIS A059442 — array of Ramsey numbers R(n,k) read by antidiagonals | website |
| REF-03 | Lean formalisation of Erdős #812 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.