Exponential growth constant for diagonal Ramsey numbers
Description of constant
$C_{17}$ is the limit (if it exists) of $R(k)^{1/k}$ as $k \to \infty$, where the diagonal Ramsey number $R(k)$ is the smallest integer $n$ such that every red/blue colouring of the edges of the complete graph $K_{n}$ contains a monochromatic copy of $K_{k}$.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $4$ | [ES1935] | |
| $4 - 2^{-7} = 4 - \frac{1}{128} = 3.9921875$ | [CGMS2023] | A simpler proof with $4 - 2^{-10}$ is also provided |
| $4 e^{-0.14/e} = 3.7992027396\dots$ | [GNNW2024] | Optimizes parameters in the [CGMS2023] approach |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $\sqrt{2} = 1.4142135623\dots$ | [Erd1947] | Introduces Erdős’ probabilistic method |
Additional comments and links
- The existence of the limit $\lim_{k\to\infty} R(k)^{1/k}$ is open. For the purposes of this page, upper (resp. lower) bounds on $C_{17}$ should be interpreted as bounding the limit superior (resp. limit inferior).
- Determining $C_{17}$’s existence and value is Erdős’ problem 77 and Ramsey theory problem 3.
- Some subexponential improvements to $R(k)$, such as [Spe1977], are not displayed on the above tables.
- A simplified proof of an upper bound of $4-c$ for some $c>0$ is given in [BBCGHMST2024].
References
- [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
- [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.
Contribution notes
ChatGPT DeepResearch was used to prepare an initial version of this page.