OpenFrontiers
Join
← Back to the index
OP-12020OpenGraph theory

Exponential growth constant of diagonal Ramsey numbers (C17C_{17})

Exponential growth constant of diagonal Ramsey numbers: determine C17C_{17} or improve its bounds; the repository records 2≈1.4142\sqrt{2} \approx 1.4142 (lower) and 3.7919936995 (upper).

MSC 05C55 · Generalized Ramsey theoryMSC 05D10 · Ramsey theory

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

C17C_{17} is the limit (if it exists) of R(k)1/kR(k)^{1/k} as k→∞k \to \infty, where the diagonal Ramsey number R(k)R(k) is the smallest integer nn such that every red/blue colouring of the edges of the complete graph KnK_{n} contains a monochromatic copy of KkK_{k}.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

  • The existence of the limit lim⁡k→∞R(k)1/k\lim_{k\to\infty} R(k)^{1/k} is open. For the purposes of this page, upper (resp. lower) bounds on C17C_{17} should be interpreted as bounding the limit superior (resp. limit inferior).
  • Determining C17C_{17}'s existence and value is Erdős' problem 77 and Ramsey theory problem 3.
  • Some subexponential improvements to R(k)R(k), such as [Spe1977], are not displayed on the above tables.
  • A simplified proof of an upper bound of 4−c4-c for some c>0c>0 is given in [BBCGHMST2024].

References (from the repository page)

  • [ES1935] Erdős, P.; Szekeres, G. A combinatorial problem in geometry. Compositio Mathematica 2 (1935), 463–470.
  • [Erd1947] Erdős, P. Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53 (1947), 292–294.
  • [Spe1977] Spencer, J. Asymptotic lower bounds for Ramsey functions. Discrete Math. 20 (1977), 69–76. DOI: 10.1016/0012-365X(77)90044-9.
  • [Tho1988] Thomason, A. An upper bound for some Ramsey numbers. J. Graph Theory 12 (1988), 509–517.
  • [Con2009] Conlon, D. A new upper bound for diagonal Ramsey numbers. Ann. of Math. (2) 170 (2009), no. 2, 941–960.
  • [Sah2023] Sah, A. Diagonal Ramsey via effective quasirandomness. Duke Math. J. 172 (2023), 545–567.
  • [CGMS2023] Campos, M.; Griffiths, S.; Morris, R.; Sahasrabudhe, J. An exponential improvement for diagonal Ramsey. arXiv:2303.09521
  • [GNNW2024] Gupta, P.; Ndiaye, N.; Norin, S.; Wei, L. Optimizing the CGMS upper bound on Ramsey numbers. arXiv:2407.19026
  • [Gri26] Max Grinsztajn. Code and certificate for a Ramsey upper bound below 3.792. GitHub repository, 2026. https://github.com/maaxgrin/ramsey-3792-bound
  • [BBCGHMST2024] Balister, P.; Bollobás, B.; Campos, M.; Griffiths, S.; Hurley, H.; Morris, R.; Sahasrabudhe, J.; Tiba, A. A shorter proof of the exponential improvement for diagonal Ramsey. arXiv:2403.02803
  • [CFS2015] Conlon, D.; Fox, J.; Sudakov, B. Recent developments in graph Ramsey theory. Surveys in Combinatorics 2015, London Math. Soc. Lecture Note Series 424, 49–118.
  • [GRS1990] Graham, R. L.; Rothschild, B. L.; Spencer, J. H. Ramsey Theory. 2nd ed., Wiley, 1990.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 2≈1.4142\sqrt{2} \approx 1.4142; best known upper bound 3.7919936995. Values marked with an asterisk have minimal verification.

Known upper bounds

Bound Reference Comments
44 [ES1935]
4−2−7=4−1128=3.99218754 - 2^{-7} = 4 - \frac{1}{128} = 3.9921875 [CGMS2023] A simpler proof with 4−2−104 - 2^{-10} is also provided
4e−0.14/e=3.7992027396…4 e^{-0.14/e} = 3.7992027396\dots [GNNW2024] Optimizes parameters in the [CGMS2023] approach
3.791993699438612<3.7923.791993699438612 < 3.792 [Gri26] Computer-assisted verification using Theorem 13 and Lemma 14 of [GNNW2024]

Known lower bounds

Bound Reference Comments
2=1.4142135623…\sqrt{2} = 1.4142135623\dots [Erd1947] Introduces Erdős’ probabilistic method
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Exponential growth constant of diagonal Ramsey numbers ($C_{17}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.