Problem 544

Show that

R(3,k+1)-R(3,k)\to\infty

as $k\to \infty$ . Similarly, prove or disprove that

R(3,k+1)-R(3,k)=o(k).

Source: erdosproblems.com/544

Graph theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

The site labels the problem OPEN. No source proves or disproves either statement, and no proof claim exists, in the search whose scope the Current assessment records. What is proved: $3\le R(3,k+1)-R(3,k)\le k+1$ for $k\ge2$ (the lower bound Graver and Yackel's Corollary 4 and the case $m=3$ of Burr, Erdős, Faudree and Schelp's Theorem 1; the upper bound the recurrence above), and the site's consequence of the ratio manuscript accepted for Problem 1014, $R(3,k+1)-R(3,k)\le k^{-c}R(3,k)=O(k^{2-c}/\log k)$ for an unspecified $c>0$ , which bounds the increment above and decides neither question. This is a bounded negative finding, not a certificate of openness.

Er81c: 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 (1981), 9--17; items (5) and (9)--(10), printed pp. 10--11. Library home: Erdős 1981.
Er88: Erdős, P., Problems and results in combinatorial analysis and graph theory. Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), Discrete Math. 72 (1988), 81--92; display (7) and the sentence after it, printed p. 84. Not a site key for this problem. Library home: Erdős 1988.
Er93: Erdős, P., Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350; the site cites p. 339. Chapter II, display (9), printed p. 339: the Erdős--Sós conjecture on $r(3,n+1)-r(3,n)$ . Library home: Erdős 1993.
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, p. 115, whose case $m=3$ the paper credits to Graver and Yackel. Library home: Theorem 1 (Burr et al. 1989).
GrYa68: Graver, J. E. and Yackel, J., Some graph theoretic results associated with Ramsey's theorem. J. Combinatorial Theory 4 (1968), 125--175; Corollary 4 and its proof, printed p. 149, the source of the lower increment $R(3,k+1)\ge R(3,k)+3$ that [BEFS89] credits to it. Library home: Corollary 4 (Graver and Yackel 1968).
OpenAI26: OpenAI, On the ratio of $R(k,\ell)$ and $R(k,\ell+1)$ . Three-page manuscript hosted at cdn.openai.com; Remark 1, p. 1; the proof is attributed by its abstract to an internal model at OpenAI. Library home: Remark 1.
Ki95: Kim, J. H., The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$ . Random Structures Algorithms 7 (1995), 173--207; the order of magnitude used below. Library home: Theorem 1.1 (Kim 1995).
Sh83: Shearer, J. B., A note on the independence number of triangle-free graphs. Discrete Math. 46 (1983), no. 1, 83--87, DOI 10.1016/0012-365X(83)90273-X; Theorem 1, printed p. 83 (PDF p. 1 of the publisher's open-archive file), the independence bound behind the upper bound $R(3,k)\le(1+o(1))k^2/\log k$ used below, with the step between them recorded on the result page. Library home: Shearer 1983; paged at Shearer 1983, Theorem 1. - OEIS A000791, Ramsey numbers $R(3,n)$ : the values $1,3,6,9,14,18,23,28,36$ for $n=1,\dots,9$ , with the comment that $R(3,10)\in\{40,41,42\}$ and a later comment (April 2024) that Angeltveit's computer search (arXiv:2401.00392, an unrefereed preprint) claims $R(3,10)\le41$ ; the entry is this page's only source for the values.

Problem 544

Status

Proof claims

Discussion