Ramsey Theory Extracts Order from Chaos when Sorting through Confusing Arrangements of Numbers

Ramsey Theory Extracts Order from Chaos when Sorting through Confusing Arrangements of Numbers

Imagine you’re hosting a small party with six guests. It’s not clear who knows who and who doesn’t. It turns out that there will be at least three people who are completely strangers to each other, or three who are already close friends. (We don’t assume that your friends are not compatible with one another. There will always be at most three people that are either completely or partially unknown to each other.

This may not sound very surprising at first but the more you look into the problem, the more fascinating it becomes. Six people have 15 connections to one another. You might wonder, “How does person A relate with person B?” How does A relate with person C? Is B acquainted with C? These connections can be 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. The math shows that there is always a trio of people who know each other or are completely strangers in every possible group. It seems a bit cumbersome to go through each case and search for a trio.

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 life, however, he was able to create a branch in mathematics that deals with identifying order in chaos. The goal is to identify recurring patterns in confusing arrangements such as the one involving our partygoers. This question can be posed mathematically: How many guests are you required to invite to ensure that there is at most one group of three people who know each other or at least one of three complete strangers?

The whole thing can be solved using figures or graphs. These are networks of points (also known as nodes) and edges. Each person represents a node. You can arrange the six guests in a circle. Each point is now connected. This creates the 15 edges. Depending on whether two people are acquaintances or strangers, they can be colored red (for friends) or blue (for enemies). The claim is that no matter what color you use to draw the edges, you always get an all-blue or all red triangle.

The additional claim made by Ramsey theory is that, regardless of how you color the edges you always get at most one monochromatic triangular figure–an all-blue, or all-red figure. You will be able to see such a triangle if you try.

Of course, nobody wants to rummage through the 32,768 possibilities. Ramsey’s question about whether six guests is enough to form a triangle would not be answered. This problem can be solved by reducing the number of guests invited. If you can find triangles that are colored in such a way that no monochromatic one appears, you will have proof. Even if you invite only three people, it is possible for two of them to have met before. In this example, there is no trio of people that are all acquainted with one another or strangers to each other. There is no monochromatic triangle.

Triangle
Credit: Spektrum der Wissenschaft/Manon Bischoff (detail)

With four people it is easy to find cases where there are no three people who are not acquainted with or friends with one another.

Square with two bisecting lines forming an X.
Credit: Spektrum der Wissenschaft/Manon Bischoff (detail)

Even with five guests, at least one configuration of friend/stranger connections exists without a triangle the same color. Ramsey’s question about the smallest partygoers who can always be represented with at least one monochromatic triangular triangle must be answered. But what about the rest?

Pentagon with five bisecting lines forming a pentagram.
Credit: Spektrum der Wissenschaft/Manon Bischoff (detail)

What happens when there are six people? Now, you must color the edges of a graph using only one-colored triangles. To do this, you will need to first choose a single person A. Then you can examine their relationship with the other guests. Let’s assume that person A is the party’s hostess. How many friends does she have among the invitees? There are six ways she can connect to the five guests. She might have one friend. In this case, there are four strangers. This chart shows six possible ways partygoers could connect with the hostess.

The table shows a party hostess’s different relationships with her fiveguests.

The hostess (personA) is friends at least with three people or more. This can be seen in a graph by the fact that she has at least three edges of the exact same color. As an example, we can see that the hostess in one configuration of the table has three red edges. This means she knows three 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.

Six dots and three red lines.
Credit: Spektrum der Wissenschaft/Manon Bischoff (detail)

You must make sure that the hostesses and any other guests don’t know eachother. They must have a blue connection. If you mark all the edges with blue, you will get a blue triangle. If all nodes must be connected, it is impossible to avoid a single-color triangular in a six-point graph. You can find such a triangular in any graph with all points connected. This means that if you invite more guests than five, there will always be a group of three people.

Six dots, three red lines and three blue lines.
Credit: Spektrum der Wissenschaft/Manon Bischoff (detail)

Mathematicians don’t like to be satisfied with one result. Instead, they try to generalize the 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, only a few Ramsey numbers have been discovered. 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. It is also unclear how large (5,5) is. 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. This task is far more difficult than any computing power.

A graph with 43 nodes that are all connected has 903 edges. These edges can be either blue (unknown) or red (friends). 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. This means that all the atoms in our universe would have been examined approximately 4. 35 x 10117 graphs to date–only a tiny fraction of what is left to process.

Mathematicians are searching for a better solution to this problem. They haven’t yet found one.

This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.

ABOUT THE AUTHOR(S)

    Manon Bischoff is an editor at Spektrum der Wissenschaft. She primarily covers mathematics and computer science and writes the column the Fabulous World of Mathematics. Bischoff studied physics at Technical University of

    Read More