A Taste of Ramsey Theory

You're at a small gathering - just five of you - and you notice something interesting. Of the possible number of handshakes - 10 in total - there have been exactly 5. More than that, in every triple of people, some have shaken hands, and some haven't.

See if you can work out a way that can happen.

At the next gathering you wonder if the same thing has happened. And here's the thing: there are six people, and it can't happen.

Claim: In every gathering of six or more people, there will either be three who have all shaken hands, or three, none of whom have shaken hands.

Every gathering.

It seems like proving that requires writing down all the ways you can have six people, but there's a lot of them. Between six people there are 15 potential handshakes, and each may or may not have happened, so there are 2^15 or 32768 possible ways things can go.

That's a lot of checking. But there's another way to see this.

Firstly, let's look at person X, and see who he/she has shaken hands with. It's either 3 or more, or less than three.

If person X has shaken hands with 3 (or more) people, then we look at that cluster. If any have shaken hands with each other, then we have our handshaking triple: person X and the other two. If none have shaken hands then they are a non-handshaking triple, and again, we have what was claimed.

The same goes if person X has shaken hands with fewer than three, we just swap shaking for not shaking, and the whole argument works.

In more colorful language, if you have six points and join every possible pair with either a blue line or a green line, you can always find a green triangle or a blue triangle. Always. But if you only have 5 points it's possible to arrange having no triangles.

Try it.

A larger gathering ...

Now for the fun bit. Suppose you look at all possible pairs of numbers, and you join them with either a blue line or a green line. Now we can always find either infinitely many points all connected by blue, or infinitely many points all connected by green.

Always.

Now this is definitely too big to check by hand, so we'll do it by logic.

Firstly, arrange all the points in a line, and look at the first point. Look at the lines going to the right, to the bigger numbers. There are infinitely many of them, so there are either infinitely many reds, in which case color the point red, or infinitely greens, in which case color the point green. If there are infinitely of each, you can choose.

The lines going to the right whose color doesn't match that of the point, delete the destination points. You still have infinitely many left.

Now move to the next point and repeat. Then again, and again, and again. Now you still have infinitely points left, each one colored, and for each point, the lines going to the right are all the same color.

You have infintely many points, and they're all green or red. If you have infintely many green, delete all the reds, otherwise delete all the greens. Now you still have infinitely many points, and they're all the same color. That means all the lines going to the right are all the same color, so all the lines are the same color.

So you have infinitely points, all joined by the same color.

Spooky.

References:
Last change to this page
Full Page history
Links to this page
 Edit this page
  (with sufficient authority)
Change password
 Recent changes
All pages
Search