by Jonathan Kujawa
There is a delightful episode of Radiolab entitled “Emergence''. In it they look at the remarkably complicated structures which can emerge from large groups of remarkably dumb individuals each doing their own thing. You see this in ant colonies, flocks of birds, human cities, capitalist marketplaces, and the human brain. Remarkably, we find the same phenomenon in the (seemingly) inert world of mathematics.
You have a problem. You're planning your annual post-New Year's party and as the consummate host you know that parties are deadly dull unless you have just the right mix of friends and strangers. A core group of witty friends or interesting strangers to keep things lively is just the thing. For the moment let's say you would be equally happy to have three people at your party who are all friends or all strangers. Unfortunately, your co-host believes parties are best when well mixed. At all costs they would like to avoid a group of three friends or three strangers.
You make a bold offer to your co-host: If you get to pick the number of guests, the co-host can decide who is invited.
Does your gambit work? Can you now successfully outmaneuver your co-host by making the invitation list sufficiently long as to ensure a group of three friends or three strangers no matter who ends up on the list? And, if so, how many? Or have you made a horrible mistake in this strange high strategy battle over the most minor of stakes?
Let's translate the scenario into something a bit more visual. Each person will be represented by a dot, a blue line will be drawn between two dots if those two people are friends, and a red line if they are strangers. For example, say you have Anne, Boris, Corey, and Dania. Then the picture might look like this:
Thus Anne and Boris are strangers, Anne and Corey are friends, and so on. In this pictorial way of looking at things, you want to ensure a triangle which is all blue or all red, and your co-host exactly wants to avoid such a thing. This example already shows that four people won't be enough. It plainly gives a configuration of friends and strangers which fails to have a monochromatic triangle.
With much labor you also find a coloring of the picture with five dots which has no monochromatic triangles. How much labor? Well, there are ten pairs of people in a group of five. Since the line between each pair can be colored blue or red, that means there is a total of 210 (1,024) possible configurations. Checking them all at a rate of one a second takes nearly three hours.
It is beginning to look like you made a bad bet. Fueled only by determination and coffee you spend the next 91 hours checking all 32,768 possible configurations of six people. In exhausted triumph you declare to your co-host that any party of six people must have a group of three who are all friends or all strangers! If you'd rather avoid such Herculean labors you can jump to the end to see a clever argument for why six is sufficient.
This calculation raises a thousand other scenarios in a curious person's mind: What if we wanted to ensure a group of four friends or three strangers, or a group of 138 friends or 76 strangers? Is it actually true that at a large enough scale nothing is avoidable?
In 1930 Frank Plumpton Ramsey answered this question as an aside to his work on a problem in logic. Ramsey was a gifted mathematician, philosopher, and economist. He died at the age of 26 and was a good friend of Wittgenstein and a student of Keynes. Sadly, Ramsey's work on our problem was published after his death and he never knew what he started. His little theorem threw open the doors to a whole new area of mathematics now called Ramsey Theory.
What did Ramsey do? In terms of the party problem, Ramsey proved that if you want to ensure a party has a group of m friends or n strangers, then there is always a number of people large enough to guarantee this outcome. Let's write R(m,n) for the smallest number which guarantees a group of m friends or a group of n strangers. The m and n are included in our notation since this number will clearly depend on the size of m and n.
In this notation your exhausting solution to the Party Problem showed that R(3,3) equals six. If instead you want to have a party with four friends or three strangers, then you would like to compute R(4,3). And to have 138 friends or 76 strangers, you need to compute R(138,76). Ramsey's astonishing result is that for any m and n, the number R(m,n) always exists!
Let's take a moment to marvel at what Ramsey did. Ramsey's theorem shows us that on large enough scales you can't avoid a bit of hidden order to the universe.
Of course, computing these numbers is something else entirely. As the number of dots in our picture increases, the possible number of colorings grows exponentially. Testing all possibilities by brute force quickly becomes impossible for even the fastest computers. Indeed, a party with twenty people will have no less than 1,569,275,433,846,670,190,958,947,355,801,916,604,025,588,861,116,008,628,224 possible friend/stranger configurations.
With a bit of cleverness people have managed to show R(4,4) is 18, R(4,5) is 25, and R(5,5) is between 43 and 49. You can see the current state of affairs on the Wikipedia page for Ramsey Theory. Computing these numbers is a notoriously hard problem. As the godfather of Ramsey Theory, Paul Erdos, put it:
Suppose an evil spirit would tell us, “Unless you tell me the value of R(5,5) I will exterminate the human race.'' Our best strategy would perhaps be to get all the computers and computer scientists to work on it. If he would ask for R(6,6) our best bet would perhaps be to try to destroy him before he destroys us.
People have since taken Ramsey's result in many directions. You can have three, four, or more colors (friends, strangers, enemies, frenemies…). You could ask to have a triangle of friends, square of strangers, or five pointed star of enemies. They have also had success in describing how fast these numbers grow. For example, Erdos showed that R(3,n) is always less than n2.
These pictures of dots and colored edges can be used to represent all sorts of scenarios with interconnected individuals: social networks, computer networks, metadata gathered by the NSA, etc. You soon see that Ramsey's theorem can be used to say all sorts of curiously fun statements. Since there are surely at least 540 actors who have worked with Kevin Bacon and since R(7,7) is no more than 540, we conclude that there are seven actors who have all worked with Kevin Bacon and have either all worked together or none worked together. Similarly, if you were to pick a Facebook member at random from each of the 50 states, then within that group would be five people who are all Facebook friends or all not. Ramsey Theory has various practical applications as well. For example, it is used by computer scientists in a variety of settings.
Ramsey also warns us against reading too much into finding unexpected structure in large data sets. By examining the various lines connecting 1,500 prehistoric locations in Britain, Tom Brooks discovered a sophisticated collection of triangles:
The designs employ Isosceles and Pythagorean triangles three millennia before their apparent discovery by Greek mathematicians…. So accurate and complex is this geometry from prehistoric time that it could not possibly have been contrived by the primitive British under testing conditions and we are witnessing the first believable evidence of extraterrestrial intervention.
— from prehistoric-geometry.co.uk
Ramsey would tell us to not get too excited. Indeed, such thinking could also easily led to the conclusion that the Woolworth stores were also built by aliens.
Lastly, back to the Party Problem. For those who don't want to check all 32,768 possibilities how can we be clever and see that every group of six must have a monochromatic triangle? Let's say the six people are Anne, Boris, Corey, Dania, Erik, and Frida. Let's think about Anne for a moment. There are five other people at the party and each one is a friend or a stranger. A moments thought leads you to see that there must be at least three of them who are all friends with Anne or all strangers with Anne. For the sake of discussion, let's say that she has three friends at the party and that they are Boris, Corey, and Erik. It doesn't matter much who they are or if the three are Anne's friends or strangers. A change of names or colors doesn't affect our reasoning. We will see it also doesn't matter if Anne is friends or strangers with Dania and Frida so let's not bother to color those edges. Here's the picture so far:
Now, if Boris and Corey are friends, then they make a friendship triangle with Anne. Same goes for Corey and Erik, and for Boris and Erik. On the other hand, if all three of these pairs are strangers, then we have our triangle of strangers! No matter the scenario, we have a friendship triangle or a stranger triangle.