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

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 $R(r,s)\leq {\binom {r+s-2}{r-1}}$. To derive this use double induction on r and s. The base case r = s = 2 is easily established as $R(2,2)=2\leq {\binom {2+2-2}{2-1}}=2$. Now assume the expression holds for R(r − 1, s) and R(r, s − 1). Then $R(r,s)\leq R(r-1,s)+R(r,s-1)\leq {\binom {r+s-3}{r-2}}+{\binom {r+s-3}{r-1}}={\binom {r+s-2}{r-1}}$ 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 ${\frac {n(R(r-1,s)-1)}{2}}$ 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

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 $2^{1-{\binom {r}{2}}}$. To see this note that there are 2 ways to color each of the ${\binom {r}{2}}$ edges and so the total possibilities for the colorings are $2^{\binom {r}{2}}$. 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 $2^{1-{\binom {r}{2}}}$.

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 ${\binom {n}{r}}$ 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 $2^{1-{\binom {r}{2}}}$, then move to another r-set, get its probability as $2^{1-{\binom {r}{2}}}$ 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 ${\binom {n}{r}}2^{1-{\binom {r}{2}}}$. 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 ${\binom {n}{r}}2^{1-{\binom {r}{2}}}$.

Now if ${\binom {n}{r}}2^{1-{\binom {r}{2}}}<1$ 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 $R(r)>n$.

Now fix r and let N be the minimum value of n satisfying ${\binom {n}{r}}2^{1-{\binom {r}{2}}}\geq 1$. 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 $R(r)\geq N$ as if $R(r)<N$ then $R(r)\leq N-1$. But this contradicts $R(r)>N-1$ which is true as ${\binom {N-1}{r}}2^{1-{\binom {r}{2}}}<1$. Hence $R(r)\geq N$.

So,

$R(r)\geq N=(N^{r})^{\frac {1}{r}}>\left({\binom {N}{r}}r!\right)^{\frac {1}{r}}\geq (2^{{\binom {r}{2}}-1}r!)^{\frac {1}{r}}=2^{{\frac {r}{2}}-{\frac {1}{2}}-{\frac {1}{r}}}(r!)^{\frac {1}{r}}$

Now use Stirlings approximation for the factorial, valid for large values of r; that is $r!\approx {\sqrt {2\pi r}}\,\left({\frac {r}{e}}\right)^{r}$. Hence for large r, on simplification we get,

$R(r)>{\frac {r2^{\frac {r}{2}}}{e{\sqrt {2}}}}(\left({\frac {\pi }{2}}\right)^{\frac {1}{2r}}r^{\frac {1}{2r}})$.

Since the terms in the brackets on the right hand side always exceed 1 so we can conclude by saying that for large r, $R(r)>{\frac {r2^{\frac {r}{2}}}{e{\sqrt {2}}}}$.

Known Ramsey numbers

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

The only two 3-colourings of K₁₆ with no monochromatic K₃.

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₁₆, 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₁₁ through v₁₅ 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₁₅ which avoid monochromatic triangles, which can be constructed by deleting any vertex from the untwisted and twisted colourings on K₁₆, respectively.

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