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 KL−1 with no blue Kr subgraph and no red Ks 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).
| “ | Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens. | ” |
|
—Joel Spencer |
||
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.
| r,s | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 3 | 1 | 3 | 6 | 9 | 14 | 18 | 23 | 28 | 36 | 40–42 |
| 4 | 1 | 4 | 9 | 18 | 25 | 36–41 | 49–61 | 56–84 | 73–115 | 92–149 |
| 5 | 1 | 5 | 14 | 25 | 43–49 | 58–87 | 80–143 | 101–216 | 126–316 | 144–442 |
| 6 | 1 | 6 | 18 | 36–41 | 58–87 | 102–165 | 113–298 | 132–495 | 169–780 | 179–1171 |
| 7 | 1 | 7 | 23 | 49–61 | 80–143 | 113–298 | 205–540 | 217–1031 | 241–1713 | 289–2826 |
| 8 | 1 | 8 | 28 | 56–84 | 101–216 | 132–495 | 217–1031 | 282–1870 | 317–3583 | 331–6090 |
| 9 | 1 | 9 | 36 | 73–115 | 126–316 | 169–780 | 241–1713 | 317–3583 | 565–6588 | 581–12677 |
| 10 | 1 | 10 | 40–42 | 92–149 | 144–442 | 179–1171 | 289–2826 | 331–6090 | 581–12677 | 798–23556 |
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.
Read more about this topic: Ramsey's Theorem
Famous quotes containing the word numbers:
“The barriers of conventionality have been raised so high, and so strangely cemented by long existence, that the only hope of overthrowing them exists in the union of numbers linked together by common opinion and effort ... the united watchword of thousands would strike at the foundation of the false system and annihilate it.”
—Mme. Ellen Louise Demorest 1824–1898, U.S. women’s magazine editor and woman’s club movement pioneer. Demorest’s Illustrated Monthly and Mirror of Fashions, p. 203 (January 1870)