Combinatorics/Bounds for Ramsey numbers

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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 Kn, with neither a red Kr nor a blue Ks. Fix this Kn in the discussion. Also fix a vertex v in Kn.

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 KR(r − 1, s) formed by these vertices. By Ramsey's theorem it should contain either a red Kr-1 or a blue Ks. It cannot contain the latter by our choice of n. Hence it contains a red Kr-1. But adjoining the vertices of this red Kr-1 to v gives us a red Kr, 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 Kn 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 Kn 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 Kn whose edges are randomly colored, red or blue, then the probability that Kr 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 Kr or a blue Kr. Hence the probability that our given Kr is monochromatic is .

Now what is the probability that there will be a monochromatic Kr 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 Kr. But it may happen that two of the chosen batches of r-sets both give monochromatic Kr'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 Kr in Kn can't exceed .

Now if then this tells us that the probability of a monochromatic Kr in Kn is less then 1 and so a monochromatic Kr in Kn 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]

The only two 3-colourings of K16 with no monochromatic K3.

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 K16, 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 v11 through v15 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 K15 which avoid monochromatic triangles, which can be constructed by deleting any vertex from the untwisted and twisted colourings on K16, respectively.

It is also known that there are exactly 115 edge colourings with 3 colours on K14 which avoid monochromatic triangles, provided that we consider edge colourings which differ by a permutation of the colours as being the same.