Do consecutive Ramsey gaps $R(3,k+1)-R(3,k)$ tend to infinity, and are they $o(k)$? (Erdős #544)
Statement
Let $R(3,k)$ be the least $N$ such that every red/blue colouring of the edges of $K_N$ contains a red triangle $K_3$ or a blue clique $K_k$. Two questions of Erdős and Sós about consecutive values: (1) show that $$R(3,k+1)-R(3,k)\to\infty$$ as $k\to\infty$; and (2) prove or disprove that $$R(3,k+1)-R(3,k)=o(k),$$ i.e. that the consecutive gaps grow strictly more slowly than linearly in $k$.
Acceptance. FULLY RESOLVES: complete proofs of both parts — (1) that $R(3,k+1)-R(3,k)\to\infty$, and (2) a proof or disproof that $R(3,k+1)-R(3,k)=o(k)$. Machine-checkable (Lean/Coq) preferred, otherwise full written proofs; settling either part alone is a substantial milestone. ADVANCES, each checkable: (a) a nontrivial unconditional lower bound showing the gap is unbounded, or eventually exceeds any explicit growing function, with proof; (b) an upper bound on the gap strictly better than the best stated in the background ($\ll k^{-c}R(3,k)$), with a complete proof; (c) extend the exact values $R(3,k)$ (OEIS A000791) by a verified computation plus certificate, tightening the empirical gap sequence. State the improvement in words and prove it strictly beats the background. Deliver the proof file, or the code plus values and certificate.
Background
A problem of Erdős and Sós [Er81c], [Er93, p.339]. It is known (Erdős #165, erdosproblems.com/165) that $R(3,k)\asymp k^2/\log k$, so the gaps average about $k/\log k$; nevertheless no unconditional bound is known even for the qualitative statement (1) that the individual differences are unbounded, and part (2) is likewise open. A recent bound recorded as Erdős #1014 (erdosproblems.com/1014; attributed on the site to OpenAI) gives $R(3,k+1)-R(3,k)\ll k^{-c}R(3,k)$ for some constant $c>0$ — a power saving of order $k^{2-c}/\log k$ on the gap, consistent with but far from the conjectured $o(k)$ (which would require the exponent to drop below $1$). This is #8 in the Ramsey Theory section of the UCSD graphs problem collection. Relevant sequence: OEIS A000791 (values of $R(3,k)$). Listed as open on erdosproblems.com/544 (fetched 2026-07-13, status 'open'), tagged graph theory | ramsey theory; no prize is attached. Attacker's tool: this is primarily a proof problem — analytic control of the triangle-free process and stability of independence numbers across consecutive $k$; the computational side-channel is extending exact values of $R(3,k)$ (OEIS A000791) via SAT/enumeration and empirically tracking the gap sequence.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #544 (T. F. Bloom) | website |
| REF-02 | OEIS A000791 — Ramsey number R(3,n) | website |
| REF-03 | Behaviour of R(3,n) — UCSD graphs problem collection (#8, Ramsey Theory) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.