Imagine you are hosting a small party for six guests, and it isn’t understood who knows one another and who doesn’t. As it turns out, there’s bound to be at least three people who are complete strangers to one another—or three who are already friends. (We’re not assuming your friends don’t like one another.) So there will always be at least one group of three people who are all either known or completely unknown to one another.
This may not sound too surprising at first, but the more you think about the problem, the more intriguing it becomes. Six people have 15 connections to one another. So, you might ask, how does person A relate to person B? How does A relate to person C? Does B know C? These connections can have one of two values: friends or strangers. This means that with just six guests, there are already 215 (32,768) different ways in which the partygoers can relate to one another. And the math makes the claim that in every possible grouping, there is always a trio in which all know one another or are otherwise complete strangers. Going through each individual case and looking for a trio seems rather cumbersome.
In fact, figuring this out falls under Ramsey theory, named after the British mathematician Frank Ramsey (1903–1930), who died at the tragically young age of 26. In his short lifetime, however, he managed to develop a branch of mathematics that deals with identifying a certain order in chaos. The aim is to recognize recurring patterns in confusing arrangements, as in the case of our partygoers. The question can be framed from a mathematical point of view: How many guests do you have to invite so that there is at least one group of three people who all know one another or at least one group of three complete strangers?
The whole thing can be solved with figures, or graphs, which are networks of points (also called nodes) and edges (the lines that connect the points). Each person symbolizes a node. The six guests can be arranged in a circle. Now each point is connected. This creates the 15 edges. Depending on whether two people know each other or not, they are colored red (for acquaintances) or blue (for strangers). Now the claim: no matter how you color the edges, you always get a monochromatic triangle—an all-blue or all-red figure.
Now the additional claim made by Ramsey theory: with the six guests just mentioned, no matter how you color the edges, you always get at least one monochromatic triangle—an all-blue or all-red figure. If you try, you will see that such a triangle always appears.
Of course, nobody wants to rummage through the 32,768 possibilities. And doing so would not answer a question posed by Ramsey as to whether six is the smallest number of guests that would inevitably form such a triangle. You can try to solve this problem by changing the number of people invited. If you find triangles colored in a way so that no monochromatic triangle appears at all, then you have found proof to the contrary. If you only invite three guests, two of the people could have met before. So in this case, there is no trio of people who are either all known or strangers to one another—hence there is no monochromatic triangle.
With four people, it is also easy to find cases in which there is no group of three who re all unknown to or else friends with one another.
Even with five guests, there is at least one configuration of friend-stranger connections without a triangle of the same color. So to answer Ramsey’s question about the smallest group of partygoers whose relationships can always be depicted with at least one monochromatic triangle, the number must be more than five. But how much more?
What happens when we get to six people? You must now try to color the edges of a graph without creating a single-colored triangle. To do this, you can first pick out a single person A and examine what their relationship to the rest of the guests might be. Let’s say person A is the party’s hostess. Among the invitees, how many friends does she have? There are six different ways of connecting her to the five guests: She might, say, have zero friends, in which case the five invitees are all strangers to her. Or she might have one friend, in which case there are four strangers. This chart shows the various ways six partygoers might connect with the hostess.
The hostess (person A) is friends with at least three people—or at least three people are unknown to her. In a graph, this can be seen by the fact that she always has at least three edges of the same color. Using a concrete example, one can assume that, in one of the configurations shown in the table, the hostess has three red edges, meaning she knows three other guests. Now you can try to color the remaining connections in such a way that a red triangle is avoided among the constellation of 32,768 possible colorings.
So you have to make sure that any two people who know the hostess, don’t know each other—they must have a blue connection between them. But if you mark all these edges in blue, you get a blue triangle! That is, there is no way to avoid a single-color triangle in a six-point graph if all the nodes must be connected. And you can find such a triangle in any larger graph where all points are connected. That means that as soon as you invite more than five guests, there is always a group of three people who all either know one another or do not group of three people who are acquaintances or complete strangers.
Of course, mathematicians are not satisfied with a single result. Instead they try to generalize a problem. So to derive a general case for Ramsey numbers, they would ask, “What is the minimum number of nodes R needs to always find a red m-clique or a blue n-clique. An n-clique denotes a group of n points that are all connected to one another. The resulting number R(m,n) is called the Ramsey number. Surprisingly, very few Ramsey numbers are known. We did just prove that R(3,3) = 6. It could also be shown that R(4,4) = 18. This means that if you invite 18 guests to a party, there will always be a group of four who all either know one another or do not.
It has been unclear for decades how large R(5,5) is, however. In other words, what is the smallest number of guests that you have to invite so that there is always a five-person grouping of all acquaintances or strangers? Experts have been able to narrow down the result: we now know that R(5,5) falls within a range that is less than or equal to 43 nodes on the lower end and less than or equal to 48 nodes at the upper boundary. It might seem like we could simply use a computer to go through all the possible colorings of graphs with 43 nodes to see if there is one that does not contain a group of five of the same color. But in fact, this task exceeds any available computing power!
A graph with 43 nodes that are all connected has 903 edges. These can be either red (friends) or blue (unknown). That’s 2903 possibilities, which is roughly 10272 when rounded off. That’s a 1 followed by 272 zeros, which is unimaginably big. In order to understand how big, one can think about it this way: it is currently assumed that our universe is made up of about 1082 atoms.
Suppose each of those atoms was a calculating machine that could perform as many calculations per second as the currently most powerful supercomputer: a quintillion (1018) calculation steps per second. Let’s assume that every atom could search a quintillion graphs for a group of five in one second—and that the particles would have started doing so right after the big bang, 13.8 billion years in the past. Then they would have had 13.8 x 109 x 365.25 x 24 x 3,600 ≈ 4.35 x 1017 seconds for this task so far. That is, all the atoms in the universe would have examined about 4.35 x 10117 graphs to date—only a tiny fraction of what is left to process.
Thus, mathematicians are looking for a smarter solution to the problem. So far, however, they haven’t found any.
This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.
