Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$

Statement

If $R(k)$ is the Ramsey number for $K_k$ (the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$), find the value of \[\lim_{k\to \infty}R(k)^{1/k}.\] (erdosproblems.com/77, statement verbatim)

Facts

- Prize \$250; status open; erdosproblems.com explicitly states "This is open, and cannot be resolved with a finite computation" (erdosproblems.com/77, fetched 2026-07-02). - Falsifiable: no — this is a statement about the asymptotic growth of an infinite sequence, not decidable by any finite search; even the *existence* of the limit is not a finite question. - Two nested sub-problems, both open: (1) does $\lim_{k\to\infty}R(k)^{1/k}$ exist at all, and (2) if so, what is its value. Erdős offered \$100 just for (1) (existence, no value needed), and separately \$1000 for a proof that the limit does *not* exist — calling that second prize "really a joke as [it] certainly exists" — later raising the relevant prize to \$10000 in [Er88]. No source found by this search proves existence; the WebSearch cross-check explicitly turned up no rigorous existence proof either. - Origin: Erdős, across [Er61], [Er69b], [Er71,p.99], [Er81], [Er88,p.83], [Er90b,p.17], [Er93,p.338], [Er95], [Er97c], [Er97d]; also Vaughan's list [Va99,3.50]. Listed as #3 in the "Ramsey Theory" section of the UCSD Erdős problem collection (mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/RamseyLimit.html, linked from erdosproblems.com/77). - Erdős proved (own classical results, cited across the same reference list): \[\sqrt{2}\leq \liminf_{k\to \infty}R(k)^{1/k}\leq \limsup_{k\to \infty}R(k)^{1/k}\leq 4.\] - Lower bound $\sqrt 2^{\,k}$: Erdős's 1947 probabilistic (random-colouring + deletion/alteration) argument — the founding application of the probabilistic method in combinatorics. - Upper bound $4^k$: Erdős–Szekeres 1935, via the binomial-coefficient recursion $R(k)\le\binom{2k-2}{k-1}$. - Known results / best bounds on the *upper* side (all verified by reading the arXiv abstracts directly): - Campos, Griffiths, Morris, Sahasrabudhe, "An exponential improvement for diagonal Ramsey," arXiv:2303.09521 (2023), published Annals of Mathematics 203(3), 2026 — proved $R(k)\le(4-\varepsilon)^k$ for an explicit constant $\varepsilon>0$ (stated on erdosproblems.com as $4-\tfrac1{128}$); the first exponential improvement over Erdős–Szekeres in 90 years. Technique: a "book algorithm" (a randomized greedy procedure for finding large monochromatic "books" — vertex sets with many common neighbours in one colour — used to drive a density/stability-type argument). This result has since been formalised twice: in Lean by Bhavik Mehta, and independently in Isabelle/HOL (devel.isa-afp.org/entries/Diagonal_Ramsey.html, fetched — confirms both formalisations exist and are largely independent of each other). - Gupta, Ndiaye, Norin, Wei, "Optimizing the CGMS upper bound on Ramsey numbers," arXiv:2407.19026 (2024) — replaced the book algorithm with a "simple inductive statement," yielding a shorter proof and an optimized bound $R(k,k)\le (3.8)^{k+o(k)}$ (erdosproblems.com states the resulting numeric constant as $3.7992\cdots$); the same method gives improved off-diagonal and multicolor bounds. - Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, Tiba, "Upper bounds for multicolour Ramsey numbers," arXiv:2410.17197 (2024) — a shorter, more elementary proof of an upper bound of strength $4-c$ (some $c>0$) that generalises to $r$ colours: $R_r(k)\le e^{-\delta k}r^{rk}$ for a constant $\delta=\delta(r)>0$; for $r\ge3$ this is itself the first exponential improvement over Erdős–Szekeres in the multicolor setting, and for $r=2$ it is an independent, shorter re-derivation of the CGMS result. - Known results on the *lower* side: no improvement to the base constant $\sqrt2$ found. erdosproblems.com's remarks (last edited 08 Feb 2026, i.e. after all three upper-bound papers above) mention only the upper-bound sequence of improvements and do not record any change to $\sqrt2$. A closely related but distinct question — improving the *polynomial* factor multiplying $2^{k/2}$ (not the exponential base) — is Erdős #1029 — polynomial-factor lower bound $R(k)/(k2^{k/2})\\to\\infty$ ($R(k)/(k2^{k/2})\to\infty$), still open, \$100. Recent 2025–2026 exponential lower-bound breakthroughs for off-diagonal Ramsey numbers $r(\ell,C\ell)$ with fixed $C>1$ — Ma, "An exponential improvement for Ramsey lower bounds," arXiv:2507.12926 (2025), and the follow-up "Sharper Ramsey lower bounds from refined Gaussian estimates," arXiv:2605.25843 (2026) — explicitly parametrize their gain by $C$ and do not claim (nor, on the stated formulas, obviously extend to) the balanced diagonal case $C=1$; treat any claim that these touch $\sqrt2$ as unverified. - Formalization: no Lean statement of problem #77 itself exists in google-deepmind/formal-conjectures (per the teorth/erdosproblems README table row for #77, fetched); only the CGMS23 upper-bound sub-result (not the full liminf/limsup/existence problem) has been formalised, and only as a standalone theorem, not as a formal statement of erdosproblems.com/77. - No entry for problem 77 in the github.com/teorth/erdosproblems wiki "AI contributions to Erdős problems" page (fetched in full 2026-07-02) — no AI system is recorded as having attempted this problem. - Related OEIS sequence: A059442 (per teorth/erdosproblems README). - Related problems: Erdős #1029 — polynomial-factor lower bound $R(k)/(k2^{k/2})\\to\\infty$ — refining the lower-bound rate (polynomial factor, not exponential base); erdos/627 — "the limit in this question is closely related to the limit" (erdosproblems.com's own words) in $f(n)=\max_G \chi(G)/\omega(G)$, i.e. the analogous growth-rate question for the chromatic-number/clique-number gap.

Literature state

Not resolved anywhere found — genuinely open, both for existence and for value. The problem has however seen the single biggest structural advance in diagonal Ramsey theory in 90 years during 2023–2024, entirely on the upper-bound side: - Campos–Griffiths–Morris–Sahasrabudhe, arXiv:2303.09521 (2023): $R(k)\le(4-\varepsilon)^k$, first exponential improvement over Erdős–Szekeres (1935). Published in Annals of Mathematics (2026). - Gupta–Ndiaye–Norin–Wei, arXiv:2407.19026 (2024): sharpened to $R(k)\le 3.8^{k+o(k)}$ via a simplified inductive replacement for the "book algorithm," and extended to off-diagonal/multicolor settings. - Balister–Bollobás–Campos–Griffiths–Hurley–Morris–Sahasrabudhe–Tiba, arXiv:2410.17197 (2024): a shorter, unified multicolor proof, giving the first exponential improvement for $r\ge3$ colours and an alternative shorter proof for $r=2$. - The CGMS23 upper-bound theorem itself has been machine-formalised twice — Lean (Bhavik Mehta) and Isabelle/HOL (devel.isa-afp.org/entries/Diagonal_Ramsey.html, "largely independent" of the Lean version) — evidence that even proofs at this frontier are within reach of current formalization tooling, though nobody has formalised the *full* statement of #77 (existence + liminf=limsup+value).

On the lower-bound side the picture is essentially frozen at Erdős's 1947 $\sqrt2^{\,k}$: no paper found in this search improves the exponential base for the balanced/diagonal case. The nearest recent activity — Ma (arXiv:2507.12926, 2025) and the follow-up refined-Gaussian-estimate paper (arXiv:2605.25843, 2026) — gives the first exponential improvements to lower bounds for the *off-diagonal* $r(\ell,C\ell)$, $C>1$ fixed, building on Ma–Shen–Xie's original break of the "Erdős barrier" and a simplified Gaussian-random-graph proof by Hunter–Milojević–Sudakov (both referenced in the 2605.25843 abstract, itself read directly). Whether this machinery has any bearing on $C=1$ (the actual diagonal case needed for #77) is not stated in either abstract and is not verified here — flagged as the most promising near-term research lead rather than an established fact.

No WebSearch result surfaced a rigorous proof that $\lim_{k\to\infty}R(k)^{1/k}$ exists (i.e. that liminf = limsup); erdosproblems.com's own remarks (last edited Feb 2026) likewise report no resolution of the \$100 existence sub-prize. Conclusion: problem #77 remains open on both axes (existence and value), even though the *quantitative bracket* $[\sqrt2,\,3.7992\ldots]$ has been meaningfully tightened since 2023 — the first movement on the upper end since 1935.

Attack surface

- Mode: derivation+formalization (not finite-search — an asymptotic statement about an infinite sequence; even a full resolution of only the *existence* sub-question, worth Erdős's original \$100, requires a general argument, e.g. a genuine subadditivity/supermultiplicativity property of $R(k)^{1/k}$, not a computation). - Concrete first experiment: (1) Formalize the *existence* sub-question narrowly: investigate whether $\log R(k)$ is (approximately) subadditive or admits a Fekete-type argument forcing $\lim (\log R(k))/k$ to exist — this is a much smaller target than the full value problem and, per this search, appears genuinely untouched (worth re-checking directly against Fekete's subadditive lemma literature, which was not itself searched in this pass). (2) Read the CGMS23/GNNW24/BBCGHMST24 "book algorithm" → "inductive statement" machinery closely (all three are open-access on arXiv) to check whether any step of the *upper*-bound argument dualizes into a lower-bound density-increment argument for the diagonal case, analogous to how Ma's off-diagonal exponential lower-bound improvement (arXiv:2507.12926) works for $C>1$ — the open question of whether that machinery degenerates gracefully as $C\to1$ is concrete and checkable by direct calculation from the stated formula $r(\ell,C\ell)\ge(p_C^{-1/2}+\varepsilon)^\ell$, $C=\log p_C/\log(1-p_C)$. - Oracle: for any finite $k$, $R(k)$ itself is (in principle) mechanically checkable via SAT/CP-SAT search for the known small cases (this is how $R(5)$'s bounds are pinned down), but this gives zero traction on the asymptotic limit — the falsifiability is explicitly "not finite," so no finite computation, however large, resolves either the existence or value sub-question. Any proposed proof must be checked the normal mathematical way (peer review / formal proof assistant, as already done for CGMS23 in Lean and Isabelle). - Feasibility: famous-and-hard, not a target for near-term LLM-assisted resolution — this is one of the deepest open questions in Ramsey theory, actively worked on by a top research group (Campos–Griffiths–Morris–Sahasrabudhe and collaborators) with three major papers in 2023–2024 alone and continued 2025–2026 activity on the closely related off-diagonal lower-bound side. The realistic near-term angle for us is not "solve #77" but (a) tracking/summarizing the frontier (this page), (b) the narrower existence-only sub-question (Fekete-type subadditivity — genuinely smaller and possibly tractable), and (c) formalization-adjacent work (e.g. extending the existing Lean/Isabelle formalizations of CGMS23 to the newer GNNW24/BBCGHMST24 bounds, which per this search have not yet been formalized).

Related

- Erdős #1029 — polynomial-factor lower bound $R(k)/(k2^{k/2})\\to\\infty$ — $R(k)/(k2^{k/2})\to\infty$: the polynomial-factor refinement of the same lower bound, explicitly linked by erdosproblems.com as "a problem concerning a lower bound for $R(k)$", \$100, open. - erdos/627 — $\lim_n f(n)/(n/(\log_2 n)^2)$ for $f(n)=\max_G\chi(G)/\omega(G)$: erdosproblems.com states this limit is "closely related" to the limit in #77; both ask for the exact asymptotic growth rate of an extremal graph-colouring parameter. - concept/probabilistic-method — Erdős's 1947 random-colouring-plus-deletion argument giving the $\sqrt2^{\,k}$ lower bound; the founding use of this method. - concept/book-algorithm — the randomized greedy "book"-finding procedure at the core of CGMS23's upper-bound breakthrough (arXiv:2303.09521), later replaced by a simpler inductive argument in GNNW24 (arXiv:2407.19026). - concept/multicolor-ramsey-numbers — the $r$-colour generalization $R_r(k)\le e^{-\delta k}r^{rk}$ proved by Balister et al. (arXiv:2410.17197), first exponential improvement for $r\ge3$. - concept/off-diagonal-ramsey-lower-bounds — the 2025–2026 exponential lower-bound improvements for $r(\ell,C\ell)$, $C>1$ fixed (Ma, arXiv:2507.12926; refined-Gaussian follow-up, arXiv:2605.25843), the most likely near-term source of new *lower*-bound technique for the diagonal case if it can be pushed to $C\to1$. - concept/proof-formalization-lean-isabelle — CGMS23's upper bound has independent Lean (Bhavik Mehta) and Isabelle/HOL (AFP Diagonal_Ramsey) formalizations; a template for how a resolution of #77 (or a sub-part of it) would ultimately need to be verified. - concept/fekete-subadditivity — candidate technique for the still-unresolved existence-of-the-limit sub-question (Erdős's original \$100 sub-prize), not itself verified against this problem in this search.