Diagonal Ramsey numbers
edit on github · preview edits · show history · long 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)
$R(n,n) \leq (1+o(n)) 4^{n-1}/\sqrt{\pi n}$ .
(4)
$R(n,n) \leq (1+o(n)) 4^{n} n^{-O(1)\log (n)/\log\log n}$ .
(5)
$R(n,n) \geq (1+o(n)) 2^{n/2} n / (\sqrt{2}e)$ .
(6)
$R(n,n) \geq (1+o(n)) 2^{n/2} \sqrt{2} n / (e)$ .
References

David Conlon, "A new upper bound for diagonal Ramsey numbers", Annals of Mathematics, 170 (2), 941–960, (2009). (arXiv) (doi)

Paul Erdős, "Some remarks on the theory of graphs", Bull. Amer. Math. Soc., 53 (4), 292–294, (1947). (doi)

Paul Erdős and George Szekeres, "A combinatorial problem in geometry", Compositio Mathematica 2, 463-470, (1935). (doi)

Stanisław Radziszowski, "Small Ramsey Numbers", Dynamic Surveys, Electronic Journal of Combinatorics, (2011). (doi)

Joel Spencer, "Ramsey's theorem - a new lower bound", J. Combin. Theory Ser. A, 18, 108–115, (1975). (doi)