Problem 1030

Let $R(k,l)$ be the usual Ramsey number: the smallest $n$ such that if the edges of $K_n$ are coloured red and blue then there exists either a red $K_k$ or a blue $K_l$ .

Prove the existence of some $c>0$ such that

\lim_{k\to \infty}\frac{R(k+1,k)}{R(k,k)}> 1+c.

Source: erdosproblems.com/1030

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. The source results in hand are additive. Burr, Erdős, Faudree and Schelp's Theorem 1 with $m=k$ , $n=k+1$ gives $R(k+1,k)\ge R(k,k)+2k-3$ for $k\ge2$ (the site's commentary quotes $2k-5$ ), and Erdős's 1981 survey states, without giving the proof, that he, Faudree, Rousseau and Schelp had proved the superlinear gap $(R(k+1,k)-R(k,k))/k\to\infty$ ; neither says anything about the ratio, because $R(k,k)$ grows exponentially, and the 1989 authors themselves expect exponential gaps but prove none. No source bounding the ratio away from $1$ , or showing it tends to $1$ , was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

BEFS89: Burr, S. A., Erdős, P., Faudree, R. J. and Schelp, R. H., On the difference between consecutive Ramsey numbers. Utilitas Math. 35 (1989), 115--118. Theorem 1 and Corollary, p. 115; Theorem 2, p. 116; the remark on growth, p. 117. Library home: Burr et al. 1989.
Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; the site cites p. 339. Chapter II, displays (10) and (11), printed pp. 339--340: "We also conjectured that (10) $r(n+1,n)/r(n,n)>1+c$ but we could not even prove (11) $r(n+1,n)-r(n,n)>n^c$ for any $c>1$ " (as printed). Library home: Erdős 1993.
Er81: Erdős, P., Some new problems and results in graph theory and other branches of combinatorial mathematics. Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math. 885, Springer, Berlin--New York (1981), 9--17. Printed p. 11 of the typescript: displays (7) and (8) and the expected limit of the ratio. Library home: Erdős 1981.
Br26: Bradač, D., Off-diagonal Ramsey numbers. arXiv:2605.28793 (v3 16 June 2026). Context: near-diagonal lower bounds, display (5) and Theorem 1.5, p. 3. Library home: Bradač 2026.
MSX25: Ma, J., Shen, W. and Xie, S., An exponential improvement for Ramsey lower bounds. arXiv:2507.12926 (v1 17 July 2025; v2 26 April 2026). Context on $r(s,Cs)$ ; not held.

Problem 1030

Status

Proof claims

Discussion