Determine the diagonal Ramsey growth constant $\lim_{k\to\infty} R(k)^{1/k}$ (Erdős #77)
Statement
Let $R(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 copy of $K_k$. Determine the value of $$\lim_{k\to\infty} R(k)^{1/k}.$$ As a first step, prove that this limit exists.
Acceptance. FULLY RESOLVES: a complete proof determining the value of $L=\lim_{k\to\infty}R(k)^{1/k}$ (which entails proving the limit exists). For the partial Erdős prizes, either a proof that the limit exists without determining its value, or a proof that the limit does not exist. A machine-checkable proof (Lean/Coq) is preferred; otherwise a complete written proof with all steps. ADVANCES (each independently checkable): improve the best known bound on $\limsup_{k}R(k)^{1/k}$ strictly beyond the best value stated in the background (currently the upper bound $3.7992\ldots$ of Gupta–Ndiaye–Norin–Wei), or improve the lower bound strictly above $\sqrt{2}$, in each case with a complete proof; or establish a new proven relation constraining the limit (e.g. that $\liminf=\limsup$). Deliver the proof (Lean file or full written argument) stating the improved constant explicitly.
Background
One of Erdős's most celebrated problems, stated and restated across [Er61], [Er69b], [Er71, p.99], [Er81], [Er88], [Er93, p.338], [Er95]; listed as open on erdosproblems.com/77 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). Prizes: erdosproblems.com catalogues a \$250 prize for the problem; Erdős offered \$100 merely for a proof that the limit exists (without its value), and \$1000 — raised to \$10000 in [Er88] — for a proof that the limit does NOT exist, though he called the latter a joke, being certain it exists. Known bounds: Erdős proved $\sqrt{2}\leq\liminf_{k}R(k)^{1/k}\leq\limsup_{k}R(k)^{1/k}\leq 4$ (the lower bound from his probabilistic $R(k)\gg k2^{k/2}$, the upper from the Erdős–Szekeres bound $R(k)\leq\binom{2k-2}{k-1}\sim 4^k$). The upper bound stood at $4$ for decades until Campos–Griffiths–Morris–Sahasrabudhe [CGMS23] achieved the first exponential improvement, $\limsup\leq 4-\tfrac{1}{128}$; this was further improved to $3.7992\ldots$ by Gupta–Ndiaye–Norin–Wei [GNNW24]. A shorter proof of a bound of the form $4-c$ (and a multicolour generalisation) was given by Balister–Bollobás–Campos–Griffiths–Hurley–Morris–Sahasrabudhe–Tiba [BBCGHMST24]. Erdős [Er93] wrote he had 'no idea what the value should be, perhaps it is $2$ but we have no real evidence.' Related: Erdős #627 and #1029 (erdosproblems.com/627, erdosproblems.com/1029); OEIS A059442 tabulates the (mostly unknown) Ramsey numbers $R(n,k)$. Attacker's tool: this is a hard asymptotic problem with almost no direct computational purchase — $R(k)$ is known only for $k\leq 4$ — so the live frontier tools are the Erdős–Szekeres / 'book algorithm' counting arguments of CGMS/GNNW, refined analytically (with Lean formalisation a possible route for the existence half).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #77 (T. F. Bloom) | website |
| REF-02 | OEIS A059442 — array of Ramsey numbers R(n,k) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.