My latest posts can be found here:
Previous blog posts:
Additionally, some earlier writings:
With the passing of Ron Graham a few people have been in touch
with me to ask what "Ramsey Theory" is. So I've given a brief
outline, and pointers in case people want to follow up. In
truth, just stick "Ramsey Theory" into your favourite search
engine and you'll get lots to follow up and chase down (as
opposed, of course, to "follow down" or "chase up").
So here I'll try to give a little context, and an actual proof.
The basic idea is that "absolute disorder is impossible", a statement that clearly requires refinement and clarification. So here is the starting place, and some motivation.
Suppose you have four points, and join each to all the others, giving six lines in all. We don't care if the lines cross, we actually only care about the joining of the dots. This is an example of a "Graph" as in "Graph Theory", some people call it "Network Theory", and say this is an example of a "Network". The exact terms don't matter.
So we have four points (or vertices, or nodes) each joined to all the others. The connectivity is complete, and in Graph Theory this is called the complete graph on four vertices, or $K_4$.
Now we colour the lines, each one being either red or green. If they are all the same colour then the graph is "mono-chromatic". (not very original or inventive, but you don't want everything to be weird and unguessable). Here are two examples:
OK, so when we have four points and colour all the lines between them either red or green, we may or may not have a monochromatic triangle.
What about with five points? With a little work we can show that the same is true ... there might be a monochromatic triangle, or there might not be, it's all down to the colouring.
What about with six points?
This is often made into a little story, with 6 people at a party, and the claim is made that you can either find three who have all mutually shaken hands, or three who have not (or both). Or you can find three who are all "friends" on Facebook, or three who are not, or both. And so on.
But that makes it harder to generalise later, so it's perhaps best to stick with the more abstract version.
Well, let's be more general. Bear with me for a bit, or skip over this bit and come back to it later.
So Ramsey's Theorem, in particular, Ramsey's finite Theorem, says that for any positive integers $g$ and $r$, there is always a size, $n$, where in a red/green edge-coloured $K_n$ there will be either a red $K_r$, a green $K_g$, or both. This number is called $R(g,r)$, while it's true that it always exists, and it's always finite, we don't actually know most of the values. Paul Erdos related the following anecdote:
And yet, even though we know almost nothing about the finite cases, we do know something about the infinite case.
The Infinite Ramsey Theorem
So let's think about all the positive integers, and think about joining every pair with a line. So 1 is joined to 2, 3, ... 13, 14, 15, ... 23, 24, ... well, you get the idea. Likewise 2 is joined to 3, 4, 5, ..., 17, 18, 19, and well, everything. So every pair of positive integers is joined by a line.
We can think of this as $K_\infty$.
And let's colour each line either red or green. Or better yet, have someone else do it.
The problem with having someone else do it is that you don't know what they've done. But Ramsey's Infinite Theorem says this:
In other words, we will always be able to find a monochromatic $K_\infty$ within.
And now I'll show you the proof.
Let's look at the first part of the graph we have:
Got that? If there are infinitely many green lines from this node going rightwards, we look at all the red lines from this node, and delete the destinations. We also colour this node green to remember we've done it.
But what if there are not infinitely many green lines going to the right? Then there must be infinitely many red lines going to the right, so we colour this node red, and delete all the rightwards nodes connected to it with a green line.
Hang on to that ... come back and re-read in a moment.
Now the original second node might have been deleted, but we know we still have infinitely many nodes remaining, so we move on to the next one, and look at the lines going right-wards from it. We do as we did last time. If there are infinitely many greens going to the right then we keep them, delete everything hit by a red line going to the right from this node, and colour this node green. Otherwise we colour this node red, and delete all the ones connected (to the right) with a green line.
Here's a diagram:
Now we have infinitely many points, and for each of them, all the lines going to the right are the same colour. How many green points do we have?
If we have infinitely many green points then we keep them, discard the others, and now we have infinitely many points with all the lines going to the right coloured green. But that means all the lines are coloured green, and we have accomplished our goal. We have found an infinite collection of points such that all interconnecting lines are the same colour.
But what if we only have finitely many green points? Well, in that case we must have infinitely many red points, and the same thing applies!
So in either case we can find infinitely many points with all lines between them coloured the same, and that completes the proof.
So there are a few things we can do now. What about more than two colours? Can we prove the finite Ramsey Theorem from the Infinite Ramsey Theorem? What about sub-structures other than monochromatic complete graphs? And so on.
Ramsey Theory is deep, rich, and this is just a taster for the sort of questions asked. In particular, we can go back to Ron Graham and look at a specific question he was working on:
The answer is that once $D$ is big enough then yes, you can always find a planar $K_4$. How big? That's where it gets interesting.
Graham proved that it worked once $D$ was a particular size, but the size was so big he had to invent a special notation for it. If every atom in the universe was turned into ink there still wouldn't be enough to write the number, not to mention that there would be neither paper, nor someone to do the writing!
The number is now known as "Graham's Number", and for a time it was the largest number ever used in a mathematical proof.
The real number is known to be bigger than 13.
Here are some links for further reading.
Evelyn Lamb wrote a nice article about this in the Scientific American:
As you might expect, there is a Wikipedia article about Ramsey Theory. And again, as you might expect, it varies in just how readable it is. Wikipedia is, after all, ostensibly an encyclopedia, and is neither a textbook nor a popular treatment:
A Wikipedia article about Graham's Number:
Here's a NumberPhile video with Ron Graham describing the problem that gave rise to the number known as Graham's Number:
Send us a comment ...
Links on this page