Diagonal Ramsey numbers

edit · history · discussion · short url · combinatorics sequence

Numbers

$n$

$R(n,n)$

[43, 46] †

comment: The lower endpoint is Exoo's 42-vertex construction [8]; the upper endpoint is the Angeltveit-McKay computation [13].

[102, 160] †

comment: The lower endpoint is Kalbfleisch's 101-vertex construction [9]; the upper endpoint is the Angeltveit-McKay computation [12].

[205, 492] †

comment: The lower endpoint is Mathon's 204-vertex construction [11]; the upper endpoint is the Angeltveit-McKay computation [12].

[282, 1518] †

comment: The lower endpoint is Burling and Reyner's 281-vertex construction [10]; the upper endpoint is the Angeltveit-McKay computation [12].

[565, 4956] †

comment: The lower endpoint is Mathon's 564-vertex construction [11]; the upper endpoint is the Angeltveit-McKay computation [12].

10:

[798, 16064] †

comment: The lower endpoint is Mathon's 797-vertex construction [11]; the upper endpoint is the Angeltveit-McKay computation [12].

Definition

The $n$'th diagonal Ramsey number $R(n,n)$ is the least positive integer $N$ such that every blue-red edge coloring of the complete graph on $N$ vertices contains a monochromatic $n$-clique, a set of $n$ vertices all of whose edges have the same color.

Parameters

$n$

— clique size ($n \geq 1$)

Formulas

(1)

$R(n,n) \leq \binom{2n-2}{n-1}$ [3].

(2)

$R(n,n) \leq (1+o(1)) 4^{n-1}/\sqrt{\pi n}$ [3].

(3)

There is a constant $C>0$ such that, for all sufficiently large $n$, $R(n,n) \leq 4^{n} n^{-C\log n/\log\log n}$ [1].

(4)

There is an $\varepsilon>0$ such that $R(n,n) \leq (4-\varepsilon)^n$ [6].

(5)

$R(n,n)\leq (3.8)^{n+o(n)}$ [7].

(6)

$R(n,n) \geq (1+o(1)) 2^{n/2} n/(\sqrt{2}e)$ [2].

(7)

$R(n,n) \geq (1+o(1)) 2^{n/2}\sqrt{2} n/e$ [5].

Comments

(8)

Ramsey's theorem states that $R(n,n)$ exists.

(9)

Exact diagonal Ramsey numbers are known only for $1\leq n\leq4$. DS1 revision #18 records lower bounds for $11\leq n\leq23$, from $R(11,11)\geq1597$ to $R(23,23)\geq49421$ [4].

(10)

The strongest asymptotic bounds cited here are $R(n,n)\leq (3.8)^{n+o(n)}$ [7] and $R(n,n)\geq(1+o(1))2^{n/2}\sqrt{2}n/e$ [5]; the other displayed asymptotic bounds are earlier records.

References

[1]

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

[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, DS1 revision #18, April 24, 2026. (doi)

[5]

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

[6]

Marcelo Campos, Simon Griffiths, Robert Morris and Julian Sahasrabudhe, "An exponential improvement for diagonal Ramsey", Annals of Mathematics 203 (3), (2026). (arXiv) (doi)

[7]

Parth Gupta, Ndiame Ndiaye, Sergey Norin and Louis Wei, "Optimizing the CGMS upper bound on Ramsey numbers", preprint, (2024). (arXiv)

[8]

Geoffrey Exoo, "A lower bound for $R(5,5)$", Journal of Graph Theory, 13 (1), 97-98, (1989).

[9]

J. G. Kalbfleisch, Chromatic Graphs and Ramsey's Theorem, Ph.D. thesis, University of Waterloo, January 1966.

[10]

J. P. Burling and S. W. Reyner, "Some lower bounds of the Ramsey numbers $n(k,k)$", Journal of Combinatorial Theory, Series B, 13, 168-169, (1972).

[11]

R. Mathon, "Lower bounds for Ramsey numbers and association schemes", Journal of Combinatorial Theory, Series B, 42, 122-127, (1987).

[12]

Vigleik Angeltveit and Brendan D. McKay, personal communication (2024).

[13]

Vigleik Angeltveit and Brendan D. McKay, "$R(5,5)\leq46$", Journal of Graph Theory, 112 (3), 198-208, (2026). (doi)

Links

[14]

OEIS: Ramsey numbers R(n,k)

[15]

Wikipedia: Ramsey's theorem

Similar tables

Kissing numbers $\tau_n$ — the same convention: exact values where known and integer intervals where only lower and upper bounds are known

$k$-core thresholds of the Erdős-Rényi random graph — another extremal graph quantity in the database, proved from graph-theoretic threshold arguments

Data properties

Entries are of type: integer

Sources of data: [4]

How well the digits are known: proven

How they were obtained:

Not computed: every exact value or endpoint is a result recorded in DS1 revision #18 [4]. Rows $1\leq n\leq4$ are exact values. Rows $5\leq n\leq10$ are intervals between a construction proving the lower endpoint and a proof of the upper endpoint. The width is ignorance about the exact Ramsey number, not numerical error.

Table is complete: no (it holds the exact values through $n=4$ and the two-sided bounds through $n=10$ recorded in DS1 revision #18)