Combinatorics/Bounds for Ramsey numbers
The numbers R(r,s) in Ramsey's theorem (and their extensions to more than two colours) are known as Ramsey numbers. A major research problem in Ramsey theory is to find out Ramsey numbers for various values of r and s. We will derive the classical bounds here for any general Ramsey number R(r,s). This will just mean the exact value of that R(r,s) lies between the two professed bounds, the lower bound and the upper bound.
Upper bound
[edit | edit source]The upper bound is actually weaned off from the proof of Ramsey's theorem itself. Since R(r, s) ≤ R(r − 1, s) + R(r, s − 1) so this automatically gives an upper bound, although not in the closed form that we expect. The closed form expression is . To derive this use double induction on r and s. The base case r = s = 2 is easily established as . Now assume the expression holds for R(r − 1, s) and R(r, s − 1). Then gives us our upper bound. Note that we have used Pascal's relation in the last equivalence.
A slight improvement is possible if both R(r − 1, s) and R(r, s − 1) are even numbers. In that case the inequality is strict.
Result: If both R(r − 1, s) + R(r, s − 1) are even numbers then R(r, s) < R(r − 1, s) + R(r, s − 1).
Proof: Suppose R(r, s) = R(r − 1, s) + R(r, s − 1) where both R(r − 1, s) and R(r, s − 1) are even numbers. Let n = R(r − 1, s) + R(r, s − 1) − 1. Now by our choice of n there exists a complete graph on n vertices, i.e. a K_{n}, with neither a red K_{r} nor a blue K_{s}. Fix this K_{n} in the discussion. Also fix a vertex v in K_{n}.
Now clearly if the number of red edges from v is less than R(r − 1, s) − 1 and the number of blue edges is less than R(r, s − 1) − 1 then the total edges from v would be less than R(r − 1, s) + R(r, s − 1) − 2, a contradiction as v is connected with exactly R(r − 1, s) + R(r, s − 1) − 2 vertices. So either the number of red edges from v is at least R(r − 1, s) − 1 or the number of blue edges from v is at least R(r, s − 1) − 1. WLOG assume the first. Now we shall show that the number of red edges from v cannot exceed R(r − 1, s) − 1. Suppose they do. Now, pick any R(r − 1, s) of the vertices adjoined to v by red edges and consider the K_{R(r − 1, s)} formed by these vertices. By Ramsey's theorem it should contain either a red K_{r-1} or a blue K_{s}. It cannot contain the latter by our choice of n. Hence it contains a red K_{r-1}. But adjoining the vertices of this red K_{r-1} to v gives us a red K_{r}, which is also not possible. Hence, the number of red edges cannot exceed R(r − 1, s) − 1. So they must be precisely R(r − 1, s) − 1. Then the remaining number of blue edges are R(r, s − 1) − 1. In summary we can say that each vertex in our K_{n} is connected to the other n − 1 vertices by precisely R(r − 1, s) − 1 red edges and R(r, s − 1) − 1 blue edges.
The total number of red edges in K_{n} is therefore which must be an integer. However as both R(r − 1, s) and R(r, s − 1) are even numbers this is impossible. Hence the initial equality was impossible. So R(r, s) < R(r − 1, s) + R(r, s − 1).
Lower bound
[edit | edit source]The classical lower bound, by an argument given essentially by Paul Erdős, is developed below. The argument is referred to as the probabilistic method. It provides a lower bound for R(r,r), which is abbreviated to R(r).
To begin note that if we are given a set of r vertices in any K_{n} whose edges are randomly colored, red or blue, then the probability that K_{r} is monochromatic is . To see this note that there are 2 ways to color each of the edges and so the total possibilities for the colorings are . Out of these only 2 are favorable: a red K_{r} or a blue K_{r}. Hence the probability that our given K_{r} is monochromatic is .
Now what is the probability that there will be a monochromatic K_{r} if a set of r vertices is not fixed in the begining? There are ways to choose r vertices out of n. By the addition law of probability we could just take any r-vertex set, get its probability as above to be , then move to another r-set, get its probability as and so on; then we could add up all the probabilities to get the probability of getting a monochromatic K_{r}. But it may happen that two of the chosen batches of r-sets both give monochromatic K_{r}'s. This is another way of saying that the events are not necessarily mutually exclusive. So the addition theorem doesn't apply and the total probability is definitely not guaranteed to be . However by the Boole's inequality we can at least conclude that the probability that there is a monochromatic K_{r} in K_{n} can't exceed .
Now if then this tells us that the probability of a monochromatic K_{r} in K_{n} is less then 1 and so a monochromatic K_{r} in K_{n} is not guaranteed. This is just another way of saying that .
Now fix r and let N be the minimum value of n satisfying . Since the collection of numbers satisfying this inequality is non-empty; R(r) itself is an example, and is bounded below; r and any number less then r are lower bounds not belonging to this collection, so the minimum value is guaranteed to exist.
Also note that as if then . But this contradicts which is true as . Hence .
So,
Now use Stirlings approximation for the factorial, valid for large values of r; that is . Hence for large r, on simplification we get,
- .
Since the terms in the brackets on the right hand side always exceed 1 so we can conclude by saying that for large r, .
Known Ramsey numbers
[edit | edit source]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, who also found the exact value of R(4,5) (with Brendan McKay).
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 | 59–84 | 73–115 | 92–149 |
5 | 1 | 5 | 14 | 25 | 43–48 | 58–87 | 80–143 | 101–216 | 133–316 | 149–442 |
6 | 1 | 6 | 18 | 36–41 | 58–87 | 102–165 | 115–298 | 134–495 | 183–780 | 204–1171 |
7 | 1 | 7 | 23 | 49–61 | 80–143 | 115–298 | 205–540 | 217–1031 | 252–1713 | 292–2826 |
8 | 1 | 8 | 28 | 56–84 | 101–216 | 134–495 | 217–1031 | 282–1870 | 329–3583 | 343-6090 |
9 | 1 | 9 | 36 | 73–115 | 133–316 | 183–780 | 252–1713 | 329–3583 | 565–6588 | 581–12677 |
10 | 1 | 10 | 40–42 | 92–149 | 149–442 | 204–1171 | 292–2826 | 343-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.
A Multicolour Example: R(3,3,3) = 17
[edit | edit source]A multicolour Ramsey number is a Ramsey number using 3 or more colours. There is only one nontrivial multicolour Ramsey number for which the exact value is known, namely R(3,3,3) = 17.
Suppose that you have an edge colouring of a complete graph using 3 colours, red, yellow and green. Suppose further that the edge colouring has no monochromatic triangles. Select a vertex v. Consider the set of vertices which have a green edge to the vertex v. This is called the green neighborhood of v. The green neighborhood of v cannot contain any green edges, since otherwise there would be a green triangle consisting of the two endpoints of that green edge and the vertex v. Thus, the induced edge colouring on the green neighborhood of v has edges coloured with only two colours, namely yellow and red. Since R(3,3) = 6, the green neighborhood of v can contain at most 5 vertices. Similarly, the red and yellow neighborhoods of v can contain at most 5 vertices each. Since every vertex, except for v itself, is in one of the green, red or yellow neighborhoods of v, the entire complete graph can have at most 1 + 5 + 5 + 5 = 16 vertices. Thus, we have R(3,3,3) ≤ 17.
To see that R(3,3,3) ≥ 17, it suffices to draw an edge colouring on the complete graph on 16 vertices with 3 colours, which avoids monochromatic triangles. It turns out that there are exactly two such colourings on K_{16}, the so-called untwisted and twisted colourings. Both colourings are shown in the figure to the right, with the untwisted colouring on the top, and the twisted colouring on the bottom. In both colourings in the figure, note that the vertices are labeled, and that the vertices v_{11} through v_{15} are drawn twice, on both the left and the right, in order to simplify the drawings.
Thus, R(3,3,3) = 17.
It is known that there are exactly two edge colourings with 3 colours on K_{15} which avoid monochromatic triangles, which can be constructed by deleting any vertex from the untwisted and twisted colourings on K_{16}, respectively.
It is also known that there are exactly 115 edge colourings with 3 colours on K_{14} which avoid monochromatic triangles, provided that we consider edge colourings which differ by a permutation of the colours as being the same.