“I was floored,” said Yuval Wigderson, a mathematician at Tel Aviv University, on hearing about the new result. “I was literally shaking for half an hour to an hour.”
The Party Lines
Ramsey theory most commonly asks questions either about the integers or about graphs. A graph, in this context, refers to collections of points called nodes, connected by lines called edges, which can have properties like length or — as in the case of the Ramsey numbers — color.
A complete graph is both complicated and simple — every node is connected to every other node. The Ramsey number describes how many nodes a complete graph must contain to be forced to have a particular structure. Say the edges of a complete graph are assigned one of two colors: red or blue. And say you try to color the edges in a way that avoids connecting a group of nodes with edges of the same color. In 1930, Frank Ramsey proved that if a graph is big enough, it becomes impossible to avoid creating what mathematicians call a monochromatic clique — a group of nodes whose common edges are either all red, or all blue.
How big, exactly, must a graph be before a monochromatic clique is forced to emerge? The answer depends on the size of the clique. Ramsey showed that there exists a number, now called the Ramsey number, representing the minimum number of nodes for which a monochromatic clique of a given size must exist, no matter how the edges are colored.
But the size of the Ramsey number is hard to pin down. In 1935, five years after Ramsey showed it exists, Erdős and George Szekeres provided a new, tighter upper bound on how big the Ramsey number is for a clique of a given size. But since then, mathematicians have barely been able to improve on Erdős and Szekeres’ calculation.
To get a better intuition for what this means, consider a classic example, in which nodes represent guests at a party. Color the edge between any two guests red if they’ve met before, and blue if they haven’t. You can pick any clique size you like — invite enough people to the party, and you can’t avoid either inviting a group of people who all know one another (a clique in multiple senses of the word) or inviting a group of people who have never met before.
“The simplest thing you can have in a graph is a monochromatic clique,” said Maria Chudnovsky, a mathematician at Princeton University. “It’s kind of amazing that in every huge graph you can find a big one of those. It’s completely not clear.”
The first few Ramsey numbers are relatively simple to calculate. Let’s say you want to know the size of the smallest graph that must unavoidably hold a clique of size two, or R(2) to mathematicians. Since a complete graph with two nodes is just two nodes connected by an edge, and that edge has to be either red or blue, R(2) is 2. More generally, R(k), or the Ramsey number of k, is the minimum number of nodes beyond which a graph can’t avoid containing a clique of size k.
It isn’t so hard to show that the Ramsey number for a clique of size 3, or R(3), is 6 (see graphic). But it wasn’t until 1955 that R(4) was pinned down at 18. R(5) remains unknown — it’s at least 43 and no bigger than 48. Though these numbers are small, sifting through all of the possible colorings is out of the question, said David Conlon of the California Institute of Technology. Consider the number of colorings on a complete graph with 43 nodes. “You have 903 edges; each of those can be colored in two ways,” he explained. “So you get 2903, which is just astronomically large.”
As the size of the clique increases, the task of nailing down the Ramsey number only gets more difficult. Erdős quipped that all-out war with mathematically demanding aliens would be easier than trying to figure out R(6), which is somewhere between 102 and 165. The range of uncertainty grows quickly: According to estimates compiled by Stanisław Radziszowski, R(10) could be as small as 798 and as big as 23,556. But mathematicians’ goals reach far beyond the Ramsey number of 10. They want a formula that will give a good estimate of R(k), even — or especially — when k is extremely large.
“I don’t know of a person in combinatorics who has not thought about this problem at least a little bit,” Wigderson said. “This problem is, I think, really special.”