Ramsey Theory on Facebook

580
ramsey theory science
ramsey theory on facebook

Almost every morning, I check my Facebook to see which of my friends are celebrating their birthdays. I rarely wish them a happy birthday because it seems so impersonal to do that online. (Ironically, it always makes me feel great to get birthday wishes on Facebook from so many friends, even ones I don’t talk with often.  But I like to start my morning with a little Ramsey theory: I get excited if all the friends who share a birthday know each other or if none of them know each other.

Ramsey theory is inexplicably defined on Wikipedia as “a branch of mathematics that studies the conditions under which order must appear.” That’s rather poetic, and I think if you already know what Ramsey theory is, it seems like a good definition. But maybe an example will make it more clear what “conditions under which order must appear” means.

The go-to example for Ramsey theory is often called the theorem on friends and strangers, and it’s where I get my Facebook birthday check motivation: if there are at least six people at a party, there must be a group of three people who all know each other or three people who are all strangers.  if you want more details on why that’s factual. If you have a party with only five people at it, on the other hand, you don’t have a assurance. This blue star inside a red pentagon is proof.

What does the theorem on friends and foreigner have to do with order that must appear? The order here is the three people who are all friends or strangers, and the “must appear” is the fact that having six people at the party makes that triangle of friends or strangers obligatory.

People who study Ramsey theory would say that the Ramsey numberR(3,3)=6. The Ramsey number R(m,n) is the smallest number of people you’d have to invite to a party to be certain that m people all know each other or n people are all strangers. (The numbers m and n don’t have to be the same.) If you wanted to be sure you could find 3 mutual friends or 4 mutual strangers, you’d be asking for the Ramsey number R(3,4), which happens to be 9.

My morning Facebook rite got me wondering whether there are any attractive Ramsey theory questions I can ask about my Facebook friends. The birthday thing throws an extra layer of structure into the normal Ramsey number problem. Now instead of looking at all my friends as one big group, I’ve split them up into 366 smaller groups, one for each possible birthday. (Yes, I have friends born on Leap Day.) The question I’m inquisitive about is whether it’s necessary for any of the nodes that are the same color to be a group of mutual friends or mutual strangers. I know that it’s true for my personal group of friends, but would it have to be true for anyone with the same number of friends I have? Or to be a little more exact, I know I have days of the year with six friends who are mutual friends or mutual strangers. Is that essential for anyone who has the same number of Facebook friends I do? What is the minimum number of Facebook friends for which this has to be true?

When I thought about this for a while, I realized the birthday grouping is a red herring. Any day of the year could have between 0 and all of my friends’ birthdays on it. For some questions I have, you have to look at the rim case in which the birthdays are all the same day, and for some you have to look at the edge case where they’re maximally spread out. Either way, you don’t get questions that are much more or less interesting or difficult than the questions without dividing people up by birthday. Oh well, you win some, you misplace some.

What’s the point? It’s not just to throw a few Ramsey theory factoids at you, although I do enjoy those factoids. I just wanted to share a little way in which a little bit of math enhance my life a little. So much talk about math, mainly math education, centers on why math is useful for jobs or everyday life. We also see a fair amount of mysticism about mathematical beauty. Those are both fine, but I also just enjoy having math as another lens with which to see the world. The fact that I know a little bit about Ramsey theory means that most mornings (there are some days none of my Facebook friends have a birthday), I think about a few of my friends on their birthdays for a few extra seconds while I check to see if there’s an interesting pattern of friends or strangers in there. So far the main interesting group I’ve noticed is six mutual strangers I know born on March 5th. I’m crossing my fingers that one of these days I hit seven!