Exponential rate of diagonal Ramsey numbers: closing the gap between (√2)^k and 3.8^k
Restored to the calibrated 78/7.5/46 (the draft lowered difficulty to 74 without a reason): the book algorithm broke the upper bound, but the lower base has stood since 1947 and even existence of the limit is open. It sits above sunflowers (71) and r(4,t) (55) and below abc (85). Application value 7.5 is indirect (pseudorandomness); leverage 46 reflects its central place in extremal combinatorics.
The problem
How big must a group be to force k people who all know each other or all are strangers? The growth rate is still unknown.
- 1How many guests force a clique or strangers?
- 2Random colourings give a lower bound
- 3Step-by-step arguments give an upper bound
- 4Gap between 1.41 and 3.8 per guest remains
Definition. The Ramsey number is the least such that every red–blue colouring of the edges of the complete graph contains a monochromatic (a set of vertices with all edges the same colour). The problem is to determine the exponential growth rate , and prove it exists. Known bounds are , where the upper bound is from Gupta, Ndiaye, Norin and Wei's optimization of the argument of Campos, Griffiths, Morris and Sahasrabudhe. Erdős offered $100 for a proof that the limit exists.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- SAT solving (CDCL)Algorithm
- Step 4
- Extremal and probabilistic combinatoricsTheory · host
- Then
- Exponential rate of diagonal Ramsey numbers: closing the gap between (√2)^k and 3.8^kThe problem
State of the art
Partially resolved: an exponential gap remains. Erdős's 1947 random colouring gives R(k) > (1+o(1)) k 2^(k/2)/(e√2); Spencer (1975) doubled the constant with the Lovász Local Lemma. No improvement of the base √2 is known. The upper bound R(k) ≤ C(2k−2, k−1) ≈ 4^k of Erdős and Szekeres (1935) was improved only by subexponential factors until Campos, Griffiths, Morris and Sahasrabudhe (arXiv 2023; Annals 203 (2026)) proved R(k) ≤ (4−ε)^k via a 'book algorithm'. Gupta, Ndiaye, Norin and Wei (arXiv 2024, revised August 2026) optimized the argument to R(k) ≤ 3.8^(k+o(k)); the Erdős problems database records the base as 3.7992…. Balister et al. (2024) gave a shorter proof extending to more colours. A preprint by Lu and Wang (arXiv:2609.14525, 13 September 2026; unrefereed, with Lean 4 and Python certificate checks) claims R(k) ≤ 3.69507^k for large k by a 'retained-set descent' that still starts from a book-type bound. Small values remain open: 43 ≤ R(5,5) ≤ 46 (upper bound Angeltveit–McKay, arXiv:2409.15709).
Realistic applications
None directly. Ramsey bounds calibrate probabilistic and book-type arguments in extremal combinatorics and underlie pseudorandomness lower bounds.
What counts as solved
A refereed proof that lim R(k)^(1/k) exists and equals a determined constant, or any refereed improvement of the base √2 or 3.7992…. The unrefereed 3.69507 claim counts only once verified.
How it gets verified
Lean proofA formal proof checked by Lean 4 / Mathlib.
Statement: Erdos77.erdos_77 in ErdosProblems/77.lean (Formal Conjectures pinned at commit e754a78 (17 October 2026)): R(k)^(1/k) converges, to a value left open as erdos_77.answer, with SimpleGraph.diagonalRamsey from the corpus' Ramsey helpers (FormalConjecturesForMathlib/Combinatorics/SimpleGraph/Ramsey.lean). Improvements of either base (above √2, below 3.7992) are not yet stated in the corpus; they are written against the same definition as eventual bounds c^k ≤ diagonalRamsey k or diagonalRamsey k ≤ c^k and checked the same way. Accept when the Lean proof compiles against the pinned corpus and passes Comparator; the unrefereed 3.69507 claim counts only once verified.
Claims under verification
+ add a claimWhere the work is
New combinatorial ideas, with computer help to optimize parameters and verify.
Bottlenecks
ranked by votes- #1TheoryNo construction beating random colourings
Erdős’s 1947 random colouring, sharpened by Spencer (1975) only in the constant, has resisted all constructive and probabilistic attempts to improve the base √2 for nearly eighty years.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Sep 13, 2026Preprint claiming base 3.69507source
Lu–Wang, unrefereed, with Lean checks.
- Jul 26, 2024Base lowered to about 3.8source
Gupta–Ndiaye–Norin–Wei.
- Mar 16, 2023Exponential improvement of Erdős–Szekeressource
Campos–Griffiths–Morris–Sahasrabudhe.
- Jan 1, 1947Erdős probabilistic lower boundsource
R(k) > (√2)^k (date approximate to the year).