Some numbers are hard to compute.
In a 1990 article for Scientific American, mathematicians Ronald Graham and Joel Spencer quoted Paul Erdös as saying:
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.
It's an intriguing quote. But what the heck is a Ramsey number, and why is it so hard to calculate?
The Game of Sim
Let's start by playing a game.
The game is called Sim — a two-player game that you can play with pencil and paper. Every game of Sim is played on a "board" made from the six vertices of a hexagon:
Each player takes turns drawing an edge between a pair of vertices, but they do so with two different colors. For example, player one might use a blue pencil, and player two might use a red pencil.
The first player to join any two of their existing edges into a triangle immediately loses:
But will one player always lose? Or is it possible for the game to end in a draw? Play a few rounds of the game with a friend — or against a computer — and see if you can force a tie!
Friends and Strangers
To determine whether or not Sim can end in a draw, let's think about a different question — one that, at first glance, might not seem related at all.
Your friend messages you and says, "I want to host a party for a group of randomly selected people, but I need to make sure that either: 1) there are three people who are all mutually strangers, or 2) there are three people who are all friends with each other. I'm serving dinner, and I'm on a tight budget. What's the smallest number of people I need to invite?"
Let's see if we can help your friend out.
Since we need to guarantee at least three mutual strangers or three people who are all friends, it seems reasonable that we need to invite at least three people to the party.
But three people isn't enough to guarantee your friend's conditions are met. For example, your friend might invite two people that know each other and one that is a stranger to the other two:
Four people won't work, either. Your friend could invite two people who are friends and two people who are strangers to each other but friends with one other person at the party:
What about five people? That feels more promising because even if your friend invites two people who are friends, the remaining three people could all be mutual strangers:
But the situation isn't so simple. There are lots of ways that five people could be in stranger/friend relationships with one another. For instance, you might find a group of three people out of the five where Person 1 knows Person 2 and Person 2 knows Person 3, but Person 1 doesn't know Person 3:
You can extend this situation to five people so that everyone at the party is friends with exactly two other people and a stranger to everyone else.
How? Well, let's represent each of the five people at the party as the vertex of a pentagon and use blue edges to indicate two people are friends and red edges to indicate two people are strangers.
Join each of the vertices around the face of the pentagon using blue edges. Then connect each pair of vertices that aren't joined by a blue edge with a red edge:
The diagram must have three vertices joined into a triangle with all blue edges to have three mutual friends. The same goes for three mutual strangers, except the edges of the triangle need to be red.
But there aren't any triangles in the diagram with three edges of the same color! So inviting five people to the party won't guarantee that your friend's conditions are met.
At this point, you might be wondering if there is any number of people your friend can invite to the party so that at least three people are mutual friends or three people are mutual strangers.
Does a similar diagram rule out six people? For example, what happens if you draw the vertices of a hexagon, join all of the vertices around the face with blue edges, and then connect everything else with red edges?
Well, look at that! Our first triangle! The strategy that worked for five people fails for six, but it doesn't mean that any group of six will necessarily contain three mutual strangers.
Graphs, Edge Colorings, and Cliques
Do you notice any similarities between your friend's dinner party problem and the Game of Sim?
In both cases, we've drawn the vertices of a polygon and added blue and red edges. The difference is that in Sim, you try to avoid triangles with the same color edges, and in the dinner party problem, you want to form triangles whose edges are all the same color.
Although explaining the diagrams in terms of polygons helps us visualize the problem, it's not strictly necessary. What we've really been doing is drawing graphs — not the graphs of functions you might be familiar with from algebra, but a different kind of graph, comprised of vertices and edges. These graphs are studied in an area of mathematics called graph theory.
In particular, we've been drawing complete graphs, which are graphs with every possible edge between every pair of distinct vertices.
The Game of Sim and the dinner party problem are concerned with the inevitability of certain kinds of structures appearing whenever you color all the edges in a complete graph with two colors. These structures are called subgraphs.
A subgraph is a portion of a graph comprised of one or more of the vertices in the original graph and a subset of the edges in the original graph that connect the vertices in the subgraph.
If a subgraph is complete, it is called an \(n\)-clique, where n is the number of vertices in the subgraph.
Using the language of graph theory, you can reframe the dinner party problem as a question about graphs.
The Dinner Party Problem (Graph-Theoretical Version): Does a complete graph exist for which any red-blue coloring of its edges results in either a red 3-clique or a blue 3-clique? And if one does exist, what is the smallest one?
You can also reframe the question about whether or not the Game of Sim can end in a draw in graph-theoretical terms.
The Game of Sim (Graph-Theoretical Version): Does every red-blue coloring of the complete graph on six vertices contain either a red 3-clique or a blue 3-clique?
Frank Ramsey Joins The Party
In 1928, British philosopher and mathematician Frank Ramsey published a paper called On a Problem in Formal Logic. The subject of Ramsey's paper bears little resemblance to the dinner party problem or the Game of Sim.
But one of the results in the paper — one that was not the focus of the discussion but needed in a more important argument — showed that for a sufficiently large system, no matter how chaotic, there exists a substructure with some kind of order. This minor result became one of Ramsey's most iconic legacies, and it can be stated in graph-theoretical terms.
Ramsey's Theorem (Graph-Theoretical Version): Given any two positive integers \(r\) and \(b\), there exists a minimum number \(R(r, b)\) such that any red-blue coloring of the complete graph on \(R(r, b)\) vertices contains either a red \(r\)-clique or a blue \(b\)-clique.
The number \(R(r, b)\) is called a Ramsey number, and the notation reminds us that Ramsey numbers depend on the choice of \(r\) and \(b\).
If you set both \(r\) and \(b\) to 3, then Ramsey's Theorem looks a lot like the dinner party problem. In fact, the theorem tells you that a solution to the problem must exist! And the smallest number of vertices you need — that is, the smallest number of people your friend needs to invite to the party — is \(R(3, 3)\).
Telling your friend to invite \(R(3, 3)\) people to their party isn't particularly helpful, though. It's good to know that they can solve their problem, but they need to know the value of \(R(3, 3)\).
The analysis we did for the dinner party problem tells us that \(R(3, 3)\) is at least six. But just because we found one red-blue coloring of the edges for the complete graph on six vertices with a red 3-clique doesn't mean that all red-blue edge colorings will have that property.
Let's look at the situation in a bit more depth. First, choose any vertex in the complete graph on six vertices and call it \(v\).
The vertex \(v\) has five edges connected to it. Now, pretend that you've colored all of the edges in the graph blue or red. What can you say about the number of red and blue edges connected to \(v\)?
There are six possibilities:
- Five red edges and no blue edges
- Four red edges and one blue edge
- Three red edges and two blue edges
- Two red edges and three blue edges
- One red edge and four blue edges
- No red edges and five blue edges
In all six cases, \(v\) is connected to at least three edges of the same color. For the sake of argument, assume that \(v\) is connected to at least three red edges. (If it isn't, swap red and blue in the following argument.) Let \(x\), \(y\), and \(z\) be the vertices at the other end of those edges.
In the diagram, there are three specific edges colored red, but we could have chosen any three of the five edges connected to \(v\).
If any of the edges \(xy\), \(xz\), or \(yz\) is red, then the coloring contains a red 3-clique.
On the other hand, if none of the edges \(xy\), \(xz\), or \(yz\) is red — in other words, they are all blue — then the coloring contains a blue 3-clique.
So, any red-blue edge coloring of the complete graph on six vertices inevitably contains either a red 3-cycle or a blue 3-cycle. This means that \(R(3, 3)\) is at most six, but since we already knew that \(R(3, 3)\) is at least six, we can conclude that \(R(3, 3)\) is exactly six!
This simultaneously solves the dinner party problem and whether the Game of Sim can end in a draw.
You can tell your friend that they only need to invite six people to the party to guarantee that at least three people are mutual friends or are mutual strangers.
And since the Game of Sim iteratively colors the edges of a complete graph on six vertices red or blue, at some point, one of the players will be forced to complete a triangle whose edges are the same color.
Impossibly Difficult Numbers
Interest in Ramsey's Theorem seems to have begun when the 1953 Putnam Competition included a graph-theoretic version of the dinner party problem. The solution to the problem established that \(R(3, 3)\) is less than six, and in 1955, mathematicians Robert Greenwood and Andrew Gleason proved that \(R(3, 3)\) is equal to six.
In the same paper, Greenwood and Gleason showed that \(R(4, 4)\) is eighteen using techniques considerably more advanced than what is needed for \(R(3, 3)\).
The search for \(R(5, 5)\), and Ramsey numbers for different values of \(r\) and \(b\), was on. In 1965, H. L. Abbott published the first lower bound for \(R(5, 5)\) in his doctoral thesis, setting the value to at least thirty-eight. By 1989, the value had been raised to forty-three.
The current best upper bound for \(R(5, 5)\) is forty-eight, and it took over a decade to lower that from the previous upper bound of forty-nine. So, after more than half a century, the best estimates for \(R(5, 5)\) are:
$$ 43 \leq R(5, 5) \leq 48. $$
The situation is even worse for \(R(6, 6)\). The current best estimates are:
$$ 102 \leq R(6, 6) \leq 165. $$
Why is calculating Ramsey numbers so hard, even for small values of \(r\) and \(b\)? It's all thanks to an explosion in the number of possible edge colorings as the number of vertices grows in the complete graphs that need to be checked.
Every vertex in a complete graph on \(n\) vertices is connected to \(n-1\) edges, so adding up the edges connected to each vertex gives \(n(n-1)\) edges. But each edge is connected to two vertices, so adding up the edges this way counts each edge twice. This means that the complete graph on \(n\) vertices has \(\frac{n(n-1)}{2}\) edges.
When you color each edge in a complete graph on \(n\) vertices red or blue, you have two choices of color for each edge. So, the total number of ways that you can color the edges of the graph is:
$$ \underbrace{2 \times 2 \times \cdots \times 2}_{\frac{n(n-1)}{2} \text{ times}} = 2^{\frac{n(n-1)}{2}}. $$
That's two to the power of \(\frac{n(n-1)}{2}\). In the best case — that is, if \(R(5, 5)\) is forty-three — you need to check 2903 edge colorings to verify that every single one has at least one red 5-clique or one blue 5-clique.
2903 is roughly 10271. For comparison, astrophysicists estimate that the universe contains about 1080 atoms!
The number of edge colorings you'd need to check to compute \(R(6, 6)\) is even more staggering. At best, you'd have to check 25151 — roughly 101550 — edge colorings!
Erdös Was Right
For the last half-century, mathematicians have spent significant resources checking edge colorings of the complete graph on forty-three vertices. Each edge coloring checked has contained either a red 5-clique or a blue 5-clique. There is a consensus that \(R(5, 5)\) is likely equal to forty-three.
But why haven't we found the value yet? Erdös posed his hypothetical scenario involving alien invaders in 1990. He thought that \(R(5, 5)\) could be found within a year, assuming the fastest computers and brightest minds were working on the problem.
Since 1990, computer processors have sped up exponentially, thanks in part to Moore's Law. This "law" states that the number of transistors on a microchip doubles roughly every two years.
If we assume that this means that processor speeds also double every two years, then modern processors in 2021 are approximately 210 times faster than processors in 1990. Under these assumptions, a task that took a year to compute in 1990 should take about eight-and-a-half hours to compute today.
Of course, these are just rough estimates. They don't consider other limiting factors, such as interest in the problem and access to sufficient computing resources. And — perhaps most importantly — we haven't had an alien force threatening to obliterate us if we don't compute \(R(5, 5)\) quickly enough.
Given the exponential increase in processing power, though, and the prior work on \(R(5, 5)\), it seems feasible that we could meet the aliens' demands, perhaps in much less time than a year.
What about \(R(6, 6)\), though?
To give you some idea of how large the number of edge colorings that need to be checked is, consider that the universe has been around for about 13.77 billion years. There are 86,400 seconds in a day and, using the Gregorian year of 365.2425 days, a total of 31,556,952 seconds every year.
This means that approximately 4.34 \(\times\) 1017 seconds have elapsed since the big bang. That's 434 quadrillion seconds!
Using the best lower bound for \(R(6, 6)\), the best-case scenario means checking approximately 25151 edge colorings. That's nearly 9.3 \(\times\) 101532 times more edge colorings than seconds since the beginning of the universe!
Even if you could check one edge coloring every nanosecond, it would take you more than 2.94 \(\times\) 101516 years to check them all! And, from the looks of it, you'd need a computer with more processors than there are atoms in the universe to leverage parallel computing to knock the time needed down to a year.
Not even quantum computing offers much hope. The best algorithm for the kinds of search needed to sift through edge colorings is called Grover's Algorithm, and it can search through a space of \(N\) items in about \(\sqrt{N}\) steps.
In other words, searching through the 25151 possible edge colorings of the complete graph on six vertices would take about 22576 steps. Assuming each of those steps took about a nanosecond, you still need about 9 \(\times\) 10758 years to search through all of the edge colorings.
The numbers are mind-numbingly huge. And while it's true that not all edge colorings need to be checked — after all, mathematicians have found ways to rule out certain configurations — the scale of the numbers is so massive that, even using our best computers, we'd need an earth-shattering breakthrough in mathematics if we are to find \(R(6, 6)\) in less than a year.
Let's hope Erdös's alien invaders never pay us a visit.
Was this article helpful or enjoyable to you? If so, consider supporting me. Every little bit helps motivate me to keep producing more content.
If you'd like to get notified whenever I publish new content, you can subscribe via RSS or join my email newsletter.
Many thanks to Tariq Rashid for reading an early draft of this article and providing valuable feedback.
If you find an error in this article, you can report it here.
References
Angeltveit, V., & McKay, B. (2018). R(5, 5) ≤ 48. Journal of Graph Theory, 89, 5– 13. https://doi.org/10.1002/jgt.22235
Graham, R., & Spencer, J. (1990). Ramsey Theory. Scientific American, 112–117.
Greenwood, R., & Gleason, A. (1955). Combinatorial Relations and Chromatic Graphs. Canadian Journal of Mathematics,7, 1–7. doi:10.4153/CJM-1955-001-4
McKay, B., & Radziszowski, S. (1997). Subgraph Counting Identities and Ramsey Numbers, Journal of Combinatorial Theory, Series B, 69, Issue 2, 193–209. https://doi.org/10.1006/jctb.1996.1741
Radziszowski, S. (2011). Small Ramsey Numbers. Dynamic Surveys. Electronic Journal of Combinatorics.
The diagrams and figures in this article were created with Canva and Excalidraw.
