Formal definitions and mumbo jumbo

Ramsey's theorem states that there is a least positive integer R(t)(s1,s2,...,sk) such that if we colour the edges of a complete (i.e. with all possible edges) t-hypergraph on this many vertices with k colours then we must always have either a complete sub(hyper)graph of order s1 coloured c1, or of order s2 coloured c2 and so on. This number is known as a Ramsey number. If we have s=s1=s2=...=sk, then we shorten our notation to R(t)k(s). It is common to omit t in the case t=2. It is also common to write R(s1,s2,...,sk;t) for R(t)(s1,s2,...,sk).

The previous statement may well have been utterly meaningless to you, but do not despair, let's have a look at some examples. The common theme in all of them is that for a given n we are trying to find the minimum number of vertices of a complete graph (or hypergraph) (i.e. with all possible edges) so that if we colour the edges with some finite number of colours then we will necessarily get a complete subgraph of order n that is monochromatic , i.e. all of whose edges are a certain colour. In the course of our proofs we often look for a different order graph depending on the colour, but this is mainly because it makes the proofs easier. Ramsey originally formulated and proved this in 1930, however his proof was rather complicated (which worried him slightly). A much simpler proof was found by Erdös and Szekeres in 1935.

The Pigeonhole principle

The special case t=1 is quite simple. Here the edges of our graph are just points. So the theorem is saying that if given k colours and some numbers s1,s2,...,sk, there is some number N such that if we have N points, no matter how we colour them with k colours then we must have at least there must s1 points of colour c1 or s2 points of colour c2 etc... This is of course just a reformulation of the pigeonhole principle except that instead of putting vertices into boxes we are colouring them. For example R1N(2)=N+1: if we have colour N+1 vertices using only N colours then we have to use one of the colours twice.

The Party Problem

The case t=k=2 is more interesting, and is also easy to understand.

An easy example is as follows: Suppose there is a party with n people (easier said than done if n is large and you are a mathematician with no friends), is there a smallest value of n such that we can always find either 3 people who all know each other or 3 people none of who know each other? We can transform this into a graph theory problem quite easily, if we represent each person by a vertex and draw a red line between 2 people if they know each other, and a blue line if don't. Then finding these sets of 3 people is exactly the same as finding a red triangle or a blue triangle. The theorem tells us that such a number will always exist, even if we instead want groups of 4,5,6,... people.

It turns out that the value of n we are looking for is 6. It is easy to find counterexamples for smaller values. If we have 6 people, we start by picking a vertex, labelled pete. It is connected to 5 other vertices, so necessarily we have either at least 3 red edges, or at least 3 blue edges. Without loss of generality, we may assume that there are 3 red edges. We now look at the 3 vertices at the other end of these 3 red edges. If between any 2 of these vertices there is a red edge, then combining with our original vertex we have a red triangle. If there is no red edge between any of these 3 vertices then these 3 vertices form a blue triangle. Thus R(3,3) exists, and its value is 6.

Proof of the existence of R(m,n)

For t=k=2, we have the following result for m,n ≥ 3:

R(m,n) exists, and R(m,n)≤R(m-1,n)+R(m,n-1).
The proof of this is easy, and is similar to our handling of the special case R(3,3).

Write Kn for the complete graph of order n.
It is clear that R(m,2)=m: a complete graph on m vertices coloured red/blue is either monochromatic red, or contains at least one blue edge i.e. complete graphs of order 2.

Let s=R(m-1,n), t= R(m,n-1).
Let n=s+t, and let us consider a complete graph on n vertices, coloured red/blue. We aim to find either a red Km or a blue Kn.

We pick a vertex v, and we consider the s+t-1 edges meeting v. They are coloured red or blue, so we have either s red edges or t blue edges (if not then we have at most s-1 red edges and t-1 blue edges, which is a total of only s+t-2 edges).

If we have s red edges, then v is connected only by red edges to some Ks. By definition of s, this means that we either have a red Km-1, which together with v gives us a red Km or a blue Kn and so we are done. Similarly, we also have the result if instead we had t blue edges.

More colours!

This enables us to prove the existance of the more general R(2)(s1,s2,...,sk). The aim is exactly the same as in the previous section, except that we are now using more colours. We proceed by induction on k. The case k=2 has been handled.

Claim: R(R(s1,s2),...,sk) is an upper bound for R(s1,s2,...,sk), and hence R(s1,s2,...,sk) exists.

We use a "colour-blindness" argument. Assume for now that we cannot distinguish colours c1 and c2. R(R(s1,s2),...,sk) exists by induction. Consider a complete graph of this order. If it has a Ksi coloured ci for 3≤i≤k, then we are done. If not we have a subgraph of order R(s1,s2) coloured with the 2 colours we cannot distinguish. We return our vision to normal, then by definition of R(s1,s2) we either have an Ks1 coloured c1 or a Ks2 coloured s2 and so we are done.

The proof of the more general case with hypergraphs is not too hard. It involves reusing the previous techniques as well as a little bit of careful induction and is left as an exercise to the reader.

So how does one calculate these numbers?

With difficulty. Despite being fairly simple things, Ramsey numbers quickly become very hard to work out. What follows is the complete list of all known Ramsey numbers for the case t=k=2:

  • R(3,3)=6
  • R(3,4)=9
  • R(3,5)=14
  • R(3,6)=18
  • R(3,7)=23
  • R(3,8)=28
  • R(3,9)=36
  • R(4,4)=18
  • R(4,5)=25
An up to date list can be found at http://mathworld.wolfram.com/RamseyNumber.html

That's right, we know precisely 9 of these thingies, although bounds are known for some other Ramsey numbers, with some being quite good (e.g. 43≤R(5,5)≤49), and others rather loose (e.g. 798≤R(10,10)≤23556). There are also results giving bounds in more general cases, but the truth is that we have a tough time calculating them. Erdös once said that if a ship full of evil aliens landed on earth and demanded to know R(5,5) then the whole of mankind could probably group together and solve the problem, but if they asked for R(6,6) we might as well just welcome our new alien overlords.