Does $R(k)/(k\,2^{k/2})\to\infty$? Beat the probabilistic diagonal Ramsey lower bound (Erdős #1029)
Statement
Let $R(k)=R(k,k)$ be the diagonal Ramsey number: the least $n$ such that every $2$-colouring of the edges of the complete graph $K_n$ contains a monochromatic $K_k$. Is it true that $$\frac{R(k)}{k\,2^{k/2}}\to\infty$$ as $k\to\infty$? Equivalently, must the diagonal Ramsey number exceed the classical probabilistic lower bound of order $k\,2^{k/2}$ by a factor that grows without bound?
Acceptance. FULLY RESOLVES: a complete proof that $R(k)/(k\,2^{k/2})\to\infty$ (Erdős's $100 offer), OR a disproof showing $R(k)\leq C\,k\,2^{k/2}$ for infinitely many $k$ and some fixed constant $C$ (the ratio stays bounded — the $1000 offer); a machine-checkable proof (Lean/Coq) is preferred, otherwise a full rigorous proof. ADVANCES: any rigorous improvement of the diagonal Ramsey lower bound beyond the Spencer constant toward a super-constant factor — i.e. prove $R(k)\geq h(k)\,k\,2^{k/2}$ for some explicit $h(k)\to\infty$, strictly stronger than the best bound stated in the background, with complete proof; or an upper-bound construction bounding $R(k)/(k\,2^{k/2})$ along an infinite sequence of $k$. A finite table of Ramsey values cannot settle the asymptotic and does not qualify. Deliver the proof file or written proof with explicit constants.
Background
Stated by Erdős [Er93, p.337], who offered $100 for a proof and $1000 for a disproof — remarking that the disproof offer was 'to some extent phoney' since he was certain the statement is true. Known bounds: Erdős and Szekeres [ErSz35] proved $k\,2^{k/2}\ll R(k)\leq\binom{2k-1}{k-1}$; the probabilistic method pioneered by Erdős gives $R(k)\geq(1+o(1))\tfrac{1}{\sqrt{2}\,e}k\,2^{k/2}$, improved by a factor of $2$ by Spencer [Sp75] to $R(k)\geq(1+o(1))\tfrac{\sqrt{2}}{e}k\,2^{k/2}$. Both lower bounds sit only a constant factor above $k\,2^{k/2}$, so the conjecture asks whether that factor can be pushed to infinity — a question untouched by the recent exponential-scale improvements to the upper bound on $R(k)$. See Erdős #77 (erdosproblems.com/77) for the companion problem on $\lim R(k)^{1/k}$ and the state of the upper bounds; the related consecutive-gap questions are Erdős #812 (erdosproblems.com/812) and #1030 (erdosproblems.com/1030). Related OEIS sequence: A059442 (array of Ramsey numbers $R(n,k)$). Listed as open on erdosproblems.com/1029 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). Attacker's tool: purely proof-shaped — diagonal Ramsey numbers are known exactly only through $R(4)=18$, so no computation reaches the asymptotic; progress requires a new lower-bound method (a super-constant improvement to the probabilistic / Lovász-Local-Lemma constructions) or a structural disproof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1029 (T. F. Bloom) | website |
| REF-02 | OEIS A059442 — array of Ramsey numbers R(n,k) read by antidiagonals | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.