Diagonal Ramsey numbers
edit on github · preview edits · show history · short url · Ramsey theory extremal combinatorics combinatorics sequence
Numbers
$n$
$R(n,n)$
1:
[1, 1]
2:
[2, 2]
3:
[6, 6]
4:
[18, 18]
5:
[43, 48]
6:
[102, 165]
7:
[205, 540]
8:
[282, 1870]
9:
[565, 6588]
10:
[798, 23556]
Definition
The $n$'th diagonal Ramsey number is the least positive integer $R(n,n)$ such that any blue-red edge coloring of the complete graph on $R(n,n)$ vertices has a monochromatic $n$-clique.
Parameters
$n$
—   integer ($n \geq 0$)
(1)
Ramsey's theorem states that $R(n,n)$ exists.
(2)
$R(n,n) \leq \binom{2n-2}{n-1}$ [3].
(3)
$R(n,n) \leq (1+o(n)) 4^{n-1}/\sqrt{\pi n}$ [3].
(4)
$R(n,n) \leq (1+o(n)) 4^{n} n^{-O(1)\log (n)/\log\log n}$ [1].
(5)
$R(n,n) \geq (1+o(n)) 2^{n/2} n / (\sqrt{2}e)$ [2].
(6)
$R(n,n) \geq (1+o(n)) 2^{n/2} \sqrt{2} n / (e)$ [5].
References
[1]
David Conlon, "A new upper bound for diagonal Ramsey numbers", Annals of Mathematics, 170 (2), 941–960, (2009). (arXiv) (doi)
[2]
Paul Erdős, "Some remarks on the theory of graphs", Bull. Amer. Math. Soc., 53 (4), 292–294, (1947). (doi)
[3]
Paul Erdős and George Szekeres, "A combinatorial problem in geometry", Compositio Mathematica 2, 463-470, (1935). (doi)
[4]
Stanisław Radziszowski, "Small Ramsey Numbers", Dynamic Surveys, Electronic Journal of Combinatorics, (2011). (doi)
[5]
Joel Spencer, "Ramsey's theorem - a new lower bound", J. Combin. Theory Ser. A, 18, 108–115, (1975). (doi)