Near-diagonal Ramsey ratio: is $R(k+1,k)/R(k,k)\geq 1+c$? (Erdős #1030)
Statement
Let $R(k,l)$ be the Ramsey number: the least $n$ such that every red/blue colouring of the edges of the complete graph $K_n$ contains a red $K_k$ or a blue $K_l$. Prove that there is a constant $c>0$ with $$\lim_{k\to\infty}\frac{R(k+1,k)}{R(k,k)} > 1+c.$$ That is, the near-diagonal Ramsey number $R(k+1,k)$ should exceed the diagonal $R(k,k)$ by a fixed multiplicative factor bounded away from $1$.
Acceptance. FULLY RESOLVES: a complete proof that $\liminf_{k}R(k+1,k)/R(k,k)>1+c$ for some explicit $c>0$, or a proof that this ratio tends to $1$; a machine-checkable proof (Lean/Coq) is preferred, otherwise a full rigorous proof. ADVANCES: a rigorous improvement of the near-diagonal gap beyond the best stated bound $R(k+1,k)-R(k,k)\geq 2k-5$ — in particular a super-linear lower bound, e.g. $\geq k^{c}$ for some $c>1$ as Erdős and Sós sought — with complete proof; or a proof of the ratio bound conditional on a clearly-stated hypothesis. A finite table of Ramsey values cannot settle the asymptotic and does not qualify. Deliver the proof file or written proof with explicit bounds.
Background
A problem of Erdős and Sós, who could not even establish $R(k+1,k)-R(k,k)>k^c$ for any $c>1$. It is trivial that $R(k+1,k)-R(k,k)\geq k-2$; Burr, Erdős, Faudree, and Schelp [BEFS89] improved this to $R(k+1,k)-R(k,k)\geq 2k-5$. See Erdős #544 (erdosproblems.com/544) for the analogous $R(3,k)$ question and Erdős #1014 (erdosproblems.com/1014) for the general off-diagonal case. The diagonal companion — consecutive $R(n,n)$ — is Erdős #812 (erdosproblems.com/812), and Erdős #1029 (erdosproblems.com/1029) concerns the diagonal lower-bound factor $R(k)/(k\,2^{k/2})$. Related OEIS sequences: A000791 (Ramsey numbers $R(3,n)$) and A059442 (array of Ramsey numbers $R(n,k)$). Listed as open on erdosproblems.com/1030 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). Attacker's tool: proof-shaped — with $R(5,5)$ already unknown, no computation reaches the $k\to\infty$ ratio; progress means a new analytic lower bound on the near-diagonal gap $R(k+1,k)-R(k,k)$, pushing the linear $2k-5$ toward the polynomial $k^c$ ($c>1$) sought by Erdős and Sós, or a direct bound on the ratio.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1030 (T. F. Bloom) | website |
| REF-02 | OEIS A000791 — Ramsey numbers R(3,n) | website |
| REF-03 | OEIS A059442 — array of Ramsey numbers R(n,k) read by antidiagonals | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.