Ramsey numbers $R(k_1,\ldots,k_r)$ of complete graphs

edit · history · discussion · files · long url · combinatorics

Numbers

$r$

$k_1,\ldots,k_r$

$R(k_1,\ldots,k_r)$

3, 3:

3, 4:

3, 5:

3, 6:

3, 7:

3, 8:

3, 9:

3, 10:

[40, 41] †

3, 11:

[47, 50] †

3, 12:

[53, 59] †

3, 13:

[61, 68] †

4, 4:

4, 5:

4, 6:

[36, 40] †

4, 7:

[49, 58] †

4, 8:

[59, 79] †

4, 9:

[73, 105] †

4, 10:

[92, 135] †

4, 11:

[102, 170] †

4, 12:

[128, 210] †

4, 13:

[139, 256] †

5, 5:

[43, 46] †

5, 6:

[59, 85] †

5, 7:

[80, 133] †

5, 8:

[101, 193] †

5, 9:

[133, 282] †

5, 10:

[149, 381] †

5, 11:

[183, 511] †

5, 12:

[203, 672] †

5, 13:

[233, 860] †

6, 6:

[102, 160] †

6, 7:

[115, 270] †

6, 8:

[134, 423] †

6, 9:

[183, 651] †

6, 10:

[204, 944] †

6, 11:

[262, 1346] †

6, 12:

[294, 1855] †

6, 13:

[347, 2499] †

7, 7:

[205, 492] †

7, 8:

[219, 832] †

7, 9:

[252, 1368] †

7, 10:

[292, 2119] †

7, 11:

[405, 3197] †

7, 12:

[417, 4665] †

7, 13:

[511, 6653] †

3, 3, 3:

3, 3, 4:

3, 3, 5:

[45, 57] †

3, 3, 6:

[61, 91] †

3, 4, 4:

[55, 77] †

3, 4, 5:

[89, 157] †

4, 4, 4:

[128, 229] †

3, 3, 3, 3:

[51, 62] †

3, 3, 3, 4:

[97, 149] †

3, 3, 4, 4:

[174, 450] †

3, 4, 4, 4:

[381, 1576] †

4, 4, 4, 4:

[634, 6301] †

3, 3, 3, 3, 3:

[162, 307] †

3, 3, 3, 3, 3, 3:

[538, 1838] †

3, 3, 3, 3, 3, 3, 3:

[1698, 12861] †

Definition

The Ramsey number $R(k_1,\ldots,k_r)$ [1] [2] is the least positive integer $N$ such that every $r$-colouring of the edges of $K_N$ contains a monochromatic clique $K_{k_i}$ in some colour $i$.

Parameters

$r$

— number of colours ($r\geq 2$)

$k_1,\ldots,k_r$

— clique-size tuple (a weakly increasing tuple of $r$ positive integers, written with commas)

Formulas

(1)

$R(1,t)=1$ and $R(2,t)=t$ for every $t\geq1$.

(2)

$R(k_1,\ldots,k_r)\leq 2-r+\sum_{i=1}^r R(k_1,\ldots,k_i-1,\ldots,k_r)$, with strict inequality when the right side is even and at least one summand is even [1].

Comments

(3)

The tuple is stored weakly increasing because $R(k_1,\ldots,k_r)$ is fixed under permutations of its arguments.

(4)

The entries use the forcing convention: $R(k_1,\ldots,k_r)$ is the least $N$ that forces a monochromatic clique. Some sources use the avoidance convention: the largest order of a complete graph whose edge-colouring avoids all listed monochromatic cliques, which is one less.

(5)

DS1 defines graph Ramsey numbers using subgraphs that are not necessarily induced. For complete graphs, the non-induced subgraph condition is the usual monochromatic clique condition.

(6)

An entry written as an integer interval $[a,b]$ means that DS1 revision #18 records a construction proving $R(k_1,\ldots,k_r)\geq a$ and a proof of $R(k_1,\ldots,k_r)\leq b$.

(7)

DS1 revision #18 also records one-sided lower bounds for larger complete graph Ramsey numbers. Those are not entries here because this table stores integers and closed integer intervals.

References

[1]

Stanislaw Radziszowski, "Small Ramsey Numbers", Dynamic Surveys, Electronic Journal of Combinatorics, DS1 revision #18, April 24, 2026. (doi)

Links

[2]

Wikipedia: Ramsey's theorem

Similar tables

Diagonal Ramsey numbers — its nontrivial entries through $n=7$ are the diagonal numbers $R(n,n)$ from this table, and it carries the diagonal bounds on to $n=10$

Data properties

Entries are of type: integer

How well the digits are known: proven

Repeats values from: Diagonal Ramsey numbers

How they were obtained:

The exact values and integer intervals are transcribed from DS1 revision #18 [1]. For two colours, the lower endpoints for $R(k_1,k_2)$ with $3\leq k_1\leq7$ and $k_1\leq k_2\leq13$ are from Table Ia; the upper endpoints for $k_1=3$ are from Table Ia, and the upper endpoints for $4\leq k_1\leq7$ are the Angeltveit-McKay bounds in Table Ib.

The multicolour exact values and two-sided bounds are the values and ranges stated in section 6.1. The generator checks the diagonal rows against the diagonal Ramsey numbers and checks the recursive upper bound $R(k_1,\ldots,k_r)\leq 2-r+\sum_{i=1}^r R(k_1,\ldots,k_i-1,\ldots,k_r)$ on every multicolour interval whose upper endpoint it can check from earlier stored rows. The width of an interval is ignorance about the exact Ramsey number, not numerical error.

Table is complete: no (it holds every DS1 entry $R(k_1,k_2)$ with $3\leq k_1\leq7$ and $k_1\leq k_2\leq13$, exact where DS1 gives an exact value and as an interval otherwise, and the complete-graph multicolour exact values or explicit two-sided bounds stated in DS1 revision #18, section 6.1; it omits the trivial values involving a clique of size 1 or 2, which are given by $R(1,t)=1$ and $R(2,t)=t$)