Last month, I wrote about a little math game I play every morning on Facebook. I check to see which friends have birthdays that day and which ones know each other and which ones don’t. Usually it’s a mixture, but I get excited on days when it’s either one or the other.
The relevant branch of mathematics to this situation is called Ramsey theory. It deals with a lot of different situations in which we want to count things and see whether certain configurations (i.e. all friends or all strangers) must appear. In my post last month, I mentioned the Ramsey number, which relates to mutual friends or strangers at a party. Specifically, the Ramsey number R(m,n) is the smallest number of people you’d have to invite to a party to be guaranteed that m people all know each other or n people are all strangers. For example, if you invite six people to a party, you’re guaranteed to get a clique of three mutual friends or a group of three mutual strangers awkwardly staring at each other at the punch bowl. So R(3,3)=6.
(The friends or strangers context isn’t really necessary. We can imagine each person as a dot in a graph where two people are connected with a blue line if they know each other and a red line if they don’t.)
The limits of our knowledge about Ramsey numbers is kind of astonishing. We know R(3,3)=6 but if we’re looking for a way to guarantee just four mutual friends or strangers, we have to invite 18 people, a sizable jump. And we don’t even know the answer for five mutual friends or strangers. It’s somewhere between 43 and 49 [update: In March 2017, Vigleik Angeltveit and Brendan D. McKay lowered the upper bound for R(5,5) from 49 to 48], but we haven’t pinned it down exactly.
When I was researching my post on Ramsey theory and Facebook, I came across this quote from prolific mathematician Paul Erdős from a 1990 Scientific American article by Ronald Graham and Joel Spencer.
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.
In other words, if the aliens are looking for R(5,5), we try to figure out R(5,5). If they’re looking for R(6,6), we try to figure out how to defeat the aliens. Granted, it’s a silly hypothetical, but when has that ever stopped anyone?
Just for fun, I decided to some rough calculations and see what effect Moore’s law on computer processing power might have had on that quote. If Erdős had said it today, would he need to change the numbers? Interpreting Moore’s law to mean computation speed doubled every 18 months since 1990, computations should have sped up by about 217, or 131,072 times. That’s pretty encouraging. If we could calculate R(5,5) in a year in 1990, it would take us a few minutes today. (Remember, that’s if we used all the world’s best minds and fastest computers.)
What about R(6,6)? How much more difficult would it be than R(5,5)? We know R(5,5) is between 43 and 49. There are a lot of different ways a group of, say, 45 people could be interconnected. There are a total of 990 pairwise relationships between 45 people, and each relationship could be either friendship or strangerhood. That’s 2990, about 10298, different configurations of friends and strangers we have to sift through, looking for collections of 5 mutual friends or mutual strangers in each one. (For reference, the universe has about 1080 atoms in it.)
For six friends or strangers, we’re in bigger trouble. We know that R(6,6) is somewhere between 102 and 165. On the low end, there are on the order of 101550 possibilities to check for 102 people. That’s about 101250 times more possibilities than we were looking at with R(5,5), far outstripping the speedup factor of 131,072 we got from Moore’s law.
Now the sheer number of graphs isn’t everything. There are ways of reducing the number of possibilities you have to check. As I’m not a Ramsey theorist, I don’t know all of them, so I don’t know how much the question can be streamlined. I'm sure the number of possibilities can be reduced by many orders of magnitude, but I’m willing to bet that the 101250 number represents an obstacle that makes R(6,6) insurmountably harder than R(5,5), even if we speed up our calculations by 131,072 times.
So my verdict is that Moore’s law is a drop in the bucket compared to the computational cost of finding R(6,6). Congratulations, Zombie Erdős, you win this round! If we are ever attacked by powerful but bizarrely single-minded extraterrestrials intent on destroying the earth unless we tell them R(6,6), we’ll still have to fight them.