Ramsey's Theorem - Ramsey Numbers

The numbers R(r,s) in Ramsey's theorem (and their extensions to more than two colours) are known as Ramsey numbers. An upper bound for R(r,s) can be extracted from the proof of the theorem, and other arguments give lower bounds. (The first lower bound was obtained by Paul Erdős using the probabilistic method.) However, there is a vast gap between the tightest lower bounds and the tightest upper bounds. Consequently, there are very few numbers r and s for which we know the exact value of R(r,s). Computing a lower bound L for R(r,s) usually requires exhibiting a blue/red colouring of the graph K_L−1 with no blue K_r subgraph and no red K_s subgraph. Upper bounds are often considerably more difficult to establish: one either has to check all possible colourings to confirm the absence of a counterexample, or to present a mathematical argument for its absence. A sophisticated computer program does not need to look at all colourings individually in order to eliminate all of them; nevertheless it is a very difficult computational task that existing software can only manage on small sizes. The complexity for searching all possible graphs (via brute force) is O(2(n-1)(n-2)/2) for an upper bound of n nodes.

As described above, R(3,3) = 6. It is easy to prove that R(4,2) = 4, and, more generally, that R(s,2) = s for all s: a graph on s − 1 nodes with all edges coloured red serves as a counterexample and proves that R(s,2) ≥ s ; among colourings of a graph on s nodes, the colouring with all edges coloured red contains a s-node red subgraph, and all other colourings contain a 2-node blue subgraph (that is, a pair of nodes connected with a blue edge.) Using induction inequalities, it can be concluded that R(4,3) ≤ R(4,2) + R(3,3) − 1 = 9, and therefore R(4,4) ≤ R(4,3) + R(3,4) ≤ 18. There are only two (4,4,16) graphs (that is, 2-colourings of a complete graph on 16 nodes without 4-node red or blue complete subgraphs) among 6.4×1022 unique 2-colourings of 16-node graphs, and only one (4,4,17) graph (the Paley graph of order 17) among 2.46×1026 colourings. (This was proven by Evans, Pulham and Sheehan in 1979.) It follows that R(4,4) = 18.

The fact that R(4,5)=25 was first established by Brendan McKay and Stanisław Radziszowski in 1995.

The exact value of R(5,5) is unknown, although it is known to lie between 43 (Geoffrey Exoo) and 49 (McKay and Radziszowski) (inclusive).

McKay, Radziszowski and Exoo employed computer-assisted graph generation methods to conjecture in 1997 that R(5,5) is exactly 43. They were able to construct exactly 656 (5,5,42) graphs, arriving at the same set of graphs through different routes. None of the 656 graphs could be extended to a (5,5,43) graph.

For R(r,s) with r, s > 5, only weak bounds are available. Lower bounds for R(6,6) and R(8,8) have not been improved since 1965 and 1972, respectively.

R(r,s) for values of r and s up to 10 are shown in the table below. Where the exact value is unknown, the table lists the best known bounds. R(r,s) for values of r and s less than 3 are given by R(1,s) = 1 and R(2,s) = s for all values of s. The standard survey on the development of Ramsey number research has been written by Stanisław Radziszowski.

There is a trivial symmetry across the diagonal.

This table is extracted from a larger table compiled by Stanisław Radziszowski, except for R(4,6) ≥ 36, which was proved by Geoffrey Exoo in 2012, and for R(3,10) ≤ 42, which was proved by Jan Goedgebeur and Stanisław Radziszowski in 2012.