NumberDB$^\beta$
Advanced search
Tags
Tables
Add numbers
Help
No match in database
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$)
Comments
(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
)
Links
[6]
OEIS: Ramsey numbers R(n,k)
[7]
Wikipedia: Ramsey's theorem
Data properties
Entries are of type: integer
Sources of data:
[4]
,
[7]