Ramsey theory: most accessible math post yet

Every time I see the ‘categories’ bar on the right side of this blog I get a guilty twinge because there’s so much baking and so little math.  I like math, I really do!  I just find it easier to blog about baking, which I do to relax, than math, which I do as my job.

During my senior year of college we had this awesome program where interested seniors could give a 20-minute scholarly presentation to their peers. We’d spent four years getting to know each others’ party habits, laundry hours, cleanliness, etc. etc., and finally had a chance to find out what everyone did during those hours when we weren’t together.  I decided to talk about graph theory, which I’ve introduced in this previous post.  I basically gave this blog post as my presentation, only with a powerpoint and being dressed up in front of an audience instead of being in pajamas on my couch.  Also, funny note, that post is called Part I but I never got around to Part II… maybe eventually!  I’ll have to re-learn Schreier’s theorem.

ANOTHER TANGENT: I by NO MEANS have an encyclopedic knowledge of mathematical facts.  Some people do, but I suspect a lot of mathematicians are like me.  We “learn” something like all of us did in high school, studying it for a few weeks, taking a test or using it some way, and then forgetting it completely a few weeks later.  But some part of it stays with us, and the next time we need that fact or technique it’s easier to re-learn it.  For instance, I think it’s taken me four tries to learn linear algebra, and if you had me take a linear algebra test tomorrow I would maaaaybe get a C.  But if you told me about it and gave me a week to study I could probably ace it.  This is not because I’m smarter than the students in the class, whoever they are, but because I’ve been exposed to the material before and have acquired the skills to learn algorithms/facts/theorems quickly for short-term memory.

OK so back to Ramsey theory!  Let’s say you’re a manager of a pretty big department of some company, and you need a committee of three people.  And, in order for this committee to work well together, you have this requirement: either

1. None of the people on the committee have ever worked with anyone else on the committee before (pairwise strangers) OR
2. All three people have worked with every other person before (so pairwise, they’ve all worked together before)

And you start going through your employee records, and you look at a single person and you think darnit!  How many of these records will I have to look at to guarantee that I’ll get a committee?!

Duh-duh-DUHHHH math to the rescue!

This is the way we start approaching such problems: first, model it.  I’ll say each employee is a vertex of my graph, and draw a red edge between two vertices if they haven’t worked together before, and draw a blue edge if they have.  So here’s what we’re looking for:

1. A red triangle (so three people who are pairwise strangers)
2. A blue triangle (so three people who have all worked together before)

Next, try baby examples.  Below I drew a blue line between two students, and a blue line between two administrators, and red lines between everything else.

No triangles! Guess we’ll have to TRI again

So we don’t have any triangles.  So if you look at just 4 employee records, you aren’t guaranteed to find a committee (you still might find one, obviously).

What about five?  Well, here’s a picture proof that 5 doesn’t work:

Not satanism, just math! Though this problem can certainly bedevil you

(Convince yourself this is a proof)

What about six?  Could that be the answer?  I can certainly draw an example with six (also I could draw one with five and four and three) but is it guaranteed?  Hint: the answer is yes!

Let’s prove it.  I love this proof so much; I share it with all my non-math friends.  It’s my party trick.  That, and petting the cat.  Does that count as a party trick?

To start we need a little fact called the pigeonhole principle.  It says if you have n boxes, and n+1 pigeons, at least one box must contain two pigeons.

One of my favorite pictures of all time.

This picture illustrates the principle with n=9: the top left box contains two pigeons.  You could also have one box holding 10 pigeons and 9 boxes with zero in them.  The point of the principle is that there is always one box with at least two pigeons.

Let’s put this principle to work!  If I’m looking at one employee’s records and comparing with five others, I have two boxes: red (has not worked together) and blue (has), with five pigeons.  By the pigeonhole principle, at least one of these boxes contains three pigeons (think about this for a minute before continuing.

…

Get it?  Got it?  Good.  Ask in the comments if you don’t).

Here’s the picture:

At least three of the edges have the same color. I arbitrarily picked blue.

NOTE: I colored the two other edges black.  These guys could be blue or red (so the possibilities are 5R, 4R1B, 3R2B, 2R3B, 1R4B, or 5B).  In all of the possibilities, there’s a color that has at least three lines in it.

Now let’s look at those three guaranteed vertices that connect to our original one via edges of the same color (let’s say it’s blue).  If I want to guarantee the existence of a blue or red triangle, I must prove it has to exist.  E.g. instead of assuming the edges between these three vertices are blue, which would automatically make a blue triangle, I should assume they’re red (we’re going for worst-case scenario).

Filling it up

And here’s the end of the proof: there’s one edge left from that picture.  What color can it be?

If the dotted edge is red, then we’ve found our committee no. 1.  If it’s blue, then we’ve used option 2.

So we’ve proved that six is the number!  In math speak, since this is a fundamental problem in Ramsey theory, we say .  This is a Ramsey number (named after a mather) for red three and blue three (I’ve never heard anyone say it like that but the quote at the bottom makes no sense otherwise).

I’ll leave you with a funny quote from Paul Erdos on the problem of Ramsey numbers, taken from wikiquote.

“Suppose aliens invade the earth and threaten to obliterate it in a year’s time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world’s best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.”

I love clipart

Tags: graph, pigeonhole principle, ramsey theory