Theorem 25: Erdős’s lower bound for the Ramsey numbers

My first-year students are busily revising Probability at the moment (amongst other things).  I thought I’d write about how some of the probabilistic ideas they’ve learned can be applied to a rather different area of maths (one that at first sight seems to have nothing to do with probability).

This area of maths is called Ramsey theory, named after Frank RamseyVan der Waerden’s theorem, the topic of a previous theorem of the week, is a result in this area.  That theorem says (roughly) that if we colour numbers red or blue then we can always find a long string of evenly spaced numbers with the same colour (a monochromatic arithmetic progression).  This week I’m going to write about something with a similar flavour, but where we colour graphs rather than numbers.

So, what is a graph?  I don’t mean a graph like a bar graph or something.  This is a different sort of graph!  This sort of graph is made up of some points (called vertices), and some lines between some of those points (called edges).  Here are some examples of graphs.

Some examples of graphs

Note that we don’t allow there to be more than one edge between two vertices, and we don’t allow a vertex to be joined to itself (no loops).  The graph on the right, which has all the possible edges, is called the complete graph on four vertices, written K_4.  The complete graph on n vertices is written K_n.

What’s the analogue of colouring numbers and looking for arithmetic progressions?  We take the complete graph K_n and colour each edge red or blue.  That’s the colouring; what are the patterns?  We could look for monochromatic triangles, perhaps.  If we colour the edges of K_n red or blue, must there be a red triangle or a blue triangle?

Here’s an example of a colouring of K_5 that has no red triangle and no blue triangle.

A coloured K_5 with no monochromatic triangle

Is there a colouring of K_6 with no red triangle and no blue triangle?  I encourage you to consider this for yourself.  Either try to find such a colouring, or prove that it’s not possible…

Having thought about finding monochromatic triangles, where do we go next?  A triangle is a complete graph on three vertices, K_3, so one natural generalisation would be to look for monochromatic K_s for larger s.

It turns out (and this isn’t obvious, although I think it’s plausible), that for any s, there is some n so that however we colour the edges of K_n using red and blue, there is always a monochromatic K_s (there is always a red K_s or a blue K_s).  We call the smallest such n the Ramsey number R(s).  The fact that this number R(s) exists is called Ramsey’s theorem.  I’m not going to prove it here, because I want to move on to something else, but it has a very nice proof and I might come back to it in a future week.

Being mathematicians, once we know that R(s) exists we of course want to know how big it is.  As you might have discovered already (if you thought about the example above), R(3) = 6.  That is, we can colour K_5 using two colours in such a way that we don’t get a monochromatic triangle (we saw such a colouring above), but however we assign the colours red and blue to the edges of K_6, we get a red triangle or a blue triangle.  That’s not too hard.  However, computing Ramsey numbers gets very hard very quickly.  The value of R(4) is known to be 18, but that’s the last one that’s known exactly!  There’s a table of what’s known about small Ramsey numbers on Wikipedia.  (The Ramsey numbers we’ve discussed are down the diagonal of that table.)

OK, so finding Ramsey numbers exactly is hard.  But as I’ve discussed on this blog before (for example here), that doesn’t mean the end of the story.  It would still be interesting to have bounds (upper and lower) for these numbers.  It turns out that the proof of Ramsey’s theorem gives some sort of upper bound, although not the best possible.  But here I’d like to talk about a proof of a lower bound.  It’s not the best known lower bound, because it’s quite old and has since been improved, but it’s not bad (compared with what’s now known) and the proof is significant because it illustrates a technique called the probabilistic method.  This proof was first given by Erdős in 1947 in this paper, and I think it’s very elegant.  It’s this week’s theorem.

Theorem (Erdős) The Ramsey number R(s) is bigger than 2^{(s-1)/2}.

Let’s remind ourselves what we’re doing.  We want a lower bound for the Ramsey number R(s).  That is, we want some n (ideally as large as possible) so that we can somehow colour the edges of K_n using red and blue in such a way that we get no red K_s and no blue K_s (just as above we saw an example of a colouring of K_5 with no red triangle and no blue triangle).  We don’t actually need to see an example of such a colouring, we just need to know that one exists.  (This might seem like a slightly odd idea the first time you come across it!)  The method we’ll use will prove that such a colouring exists, but will give us no information about how to find it.  It is non-constructive.

Here’s the idea (with details to follow afterwards).  We’ll pick a random colouring of the edges of K_n.  Then we’ll get an upper bound for the probability of a monochromatic K_s.  We’ll show that if we choose n carefully, we can make that probability less than 1.  If the probability is less than 1, then there must be some colouring with no monochromatic K_s (because if every possible colouring of K_n had at least one monochromatic K_s, then the probability of a monochromatic K_s would be one).  And that will do nicely.

How do we pick a random colouring?  We colour each edge of K_n red or blue, using each colour with probability 1/2.  We colour the edges independently.

What’s the probability that we get a monochromatic K_s?  It’s certainly at most the sum of the probabilities that each K_s is monochromatic (using quite a crude bound).  We can find this by counting the total number of K_ss in K_n and multiplying by the probability that an individual K_s is monochromatic.

How many K_ss are there?  If we pick any collection of s vertices from our K_n, there’s exactly one K_s with those vertices.  So the number of K_ss is the number of ways to choose s vertices from n, which is the binomial coefficient \binom{n}{s}.

What’s the probability that a single K_s is monochromatic?  The probability that a single edge is red is \frac{1}{2}.  The graph K_s has \binom{s}{2} edges, and since the probabilities for different edges are independent we can multiply to see that the probability that K_s is red is 2^{-\binom{s}{2}}.  Also, the probability that K_s is blue is 2^{-\binom{s}{2}}, so the probability that K_s is monochromatic is the sum of those, which is 2^{1 - \binom{s}{2}}.

So the probability of a monochromatic K_s is at most \binom{n}{s} 2^{1 - \binom{s}{2}}, and we want to choose n as large as possible so that this is less than 1.  We’ve basically done all the thinking now — the rest is down to careful estimation!  I’m not going to be very careful here, so this isn’t the best possible bound that one can extract from this argument.

If we take n = \lfloor 2^{(s-1)/2} \rfloor (where the funny brackets mean we round down to the nearest whole number — we take the integer part), what do we get?  We use a crude bound for the binomial coefficient; I’ll let you convince yourself that it’s true.  The probability of a monochromatic K_s is at most 2^{1-\binom{s}{2}}\binom{n}{s}\leq 2^{1-\binom{s}{2}}\frac{n^s}{s!}<2^{-s(s-1)/2}2^{s(s-1)/2}=1, so the probability is strictly less than 1, as we wanted.  (You could look at David Conlon’s notes from his second lecture (see below) if you want to see a more careful estimate.)

If you look at Erdős’s paper, you’ll see that he phrases this argument using counting rather probability.  The reason that it tends to be phrased probabilistically nowadays is that this language allows one to use lots of other ideas from probability (such as expectation and variance and so on).  This argument is a relatively simple application of the probabilistic method, but (I hope you’ll agree) no less interesting or beautiful for that.

Further reading

There’s more information about Ramsey numbers and Ramsey theory all over the place.  For example, David Conlon is giving a lecture course on Graph Ramsey Theory in Cambridge this term, with notes online.  The standard reference for the probabilistic method is The Probabilistic Method by Alon and Spencer, which discusses the above proof and much much more!  (The proof above is really the simplest sort of application of probability to problems like this — there are more sophisticated approaches too.)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: