Disorder Persists in Larger Graphs, New Math Proof Finds

After more than 70 years of intransigence, one of the most stubborn numbers in math has finally budged.

In a four-page proof posted in late September, David Conlon and Asaf Ferber provided the most precise estimate yet for “multicolor Ramsey numbers,” which measure how large graphs can become before they inevitably exhibit certain kinds of patterns.

“There is no absolute randomness in this universe,” said Maria Axenovich of the Karlsruhe Institute of Technology in Germany. “There are always clusters of order, and the Ramsey numbers quantify it.”

Graphs are collections of dots (vertices) connected by lines (edges). Mathematicians are particularly interested in understanding how many vertices and edges they can contain before different kinds of substructures emerge within them.

“If you have a big enough graph then there is a large part of it that’s very tightly ordered,” said Maria Chudnovsky of Princeton University. “It’s hard to explain why something is beautiful, but there is universal agreement that this is a beautiful phenomenon.”

Ramsey numbers concern a particular pattern called a monochromatic clique, which is a set of vertices that are all connected to each other by edges of the same color after you perform a specific coloring procedure.

Ramsey numbers vary depending on the size of the clique you’re looking for and the number of colors you use to perform the coloring. Mathematicians can’t calculate most Ramsey numbers because all but the smallest graphs are too complex to analyze directly.

Usually, the best mathematicians can do is to set a range of possible values for Ramsey numbers. It’s as if you wanted to know a friend’s location but could only determine with certainty that they’re north of Miami and south of Philadelphia.

The new proof does more to zero in on the exact value of Ramsey numbers than any result since Paul Erdős first studied them in the 1930s and ’40s. Conlon, of the California Institute of Technology, and Ferber, of the University of California, Irvine, found a new “lower bound” for multicolor Ramsey numbers that is exponentially more precise than the previous best estimate. Their result provides mathematicians with a new understanding of the interplay between order and randomness in graphs, which are of fundamental interest in mathematics.

“This is a fantastic result,” said Axenovich. “I love it.”

Colorful Connections

Ramsey numbers, which were introduced by the British polymath Frank Ramsey in the 1920s, are best understood by example. Start with a graph with five vertices. Connect each of them to all the others to form what mathematicians call a complete graph. Now, can you color each edge red or blue without creating a set of three vertices that are all connected to each other by edges of the same color? The answer is: You can.

But start with a complete graph of six vertices, and now there’s no way to color the edges with two colors without creating a monochromatic clique of at least three vertices. Or, to put it another way, for two colors and a clique of size 3, the Ramsey number is 6 (since it requires a complete graph of six vertices).

Ramsey numbers vary depending on the number of colors and the size of the monochromatic clique you’re looking for. But in general, they’re hard to calculate exactly, and mathematicians only know exact values for a small number of situations. Even for small cliques of size 5 (and two colors), the best they can say is that the Ramsey number is between 43 and 48.

“It’s really embarrassing,” said Yuval Wigderson, a graduate student at Stanford University. “We’ve been working on this problem for close to 100 years and we don’t know anything.”

Ramsey numbers are hard to calculate because the complexity of a graph increases dramatically as you add vertices. For a graph with six vertices and two colors, you can run through all the possibilities by hand. But for a graph with 40 vertices, there are 2⁷⁸⁰ ways of applying two colors.

“There’s just too much to check,” Axenovich said.

Among mathematicians who study Ramsey numbers there’s a parable, usually credited to Erdős, that captures how quickly these calculations become forbidding. One day, hostile aliens invade. They offer to spare the planet if we can produce correct Ramsey numbers. According to the parable, if they ask for the Ramsey number for two-color cliques of size 5, we should throw all the resources of human civilization into finding it. But if they ask for a clique of size 6, we should prepare for battle.

“If they ask us for the Ramsey number of 6, then forget about it, we launch an attack,” Axenovich said.

Exploiting Randomness

Because calculating exact Ramsey numbers is largely impossible, mathematicians instead home in on them, proving they’re greater than some “lower bound” and less than some “upper bound.” The new work improves the precision of lower bounds but doesn’t address upper bounds.

In 1935, Erdős and George Szekeres established the first such bound. They used a short proof to show that two-color Ramsey numbers must be smaller than an upper bound of 4^t, where t is the size of the monochromatic clique you’re interested in. They also found that three-color Ramsey numbers must be smaller than 27^t. A decade later, in 1947, Erdős calculated the first lower bounds for these numbers: For two colors it’s ($latex \sqrt{2}$)^t vertices and for three colors it’s ($latex \sqrt{3}$)^t.

There is a big difference between ($latex \sqrt{2}$)^t and 4^t, especially as t gets very large. This gap reflects mathematicians’ imprecise understanding of Ramsey numbers. But the form of the bounds — the way the size of the requisite graph is expressed in terms of the size of the desired clique — hints at what mathematicians most want to know.

“What we’d really like to understand is the growth behavior of these [Ramsey] numbers as the size of the clique grows,” said Lisa Sauermann, a postdoctoral fellow at the Institute for Advanced Study in Princeton, New Jersey.

For this reason, Erdős’ most enduring contribution to the study of Ramsey numbers was not the bounds themselves — it was the method he used to calculate them. Here’s what he did for the lower bound.

Imagine you have a complete graph with 10 vertices and 45 edges. And imagine you want to know whether it’s possible to apply three colors without creating a monochromatic clique of some specific size, say five vertices (connected by 10 edges).

You can start, as Erdős did, by coloring the edges at random. For each edge, roll the equivalent of a three-sided die and apply whichever color comes up. Erdős knew that the probability that any particular subset of 10 edges will end up all the same color is easy to calculate. It’s just the probability that one edge is, say, red, times the probability that another edge is red, and so on for all 10 edges (so 1/3¹⁰). Next, he multiplied that value by 3 to account for the fact that there are three different colors that could produce the desired monochromatic clique.

Erdős then looked at the total number of different cliques of five vertices in the graph. There are 252 of them. Finally, he took the probability that one of them will yield a monochromatic clique and added it to the probabilities that any of the other 251 will produce the clique. This is a calculation known as taking the “union bound,” and it estimates the probability of producing a monochromatic clique when you color the edges at random.

As long as the union bound remains below 1, you know the random coloring method is not guaranteed to produce the given monochromatic clique. In our example, the union bound is 0.0128. This means you’re far from being guaranteed a monochromatic clique of 5 vertices, which means the Ramsey number for this example is larger than 10 vertices.

Mathematicians call this approach the probabilistic method. It’s an ingenious workaround for an otherwise intractable problem. Instead of having to find examples of colorings that don’t contain monochromatic cliques of different sizes, Erdős simply proved that these clique-less colorings must exist (because the union bound is less than 1) — meaning the Ramsey number has to be larger than the number of vertices in the graph you’re currently coloring at random.

“We’re able to prove that something exists without actually showing what it is,” Wigderson said.

Over the next 70 years, mathematicians improved on Erdős’ lower bound for two and three colors just once — in 1975, with an incremental tightening by Joel Spencer. Many people worked on the problem, but none could find a better way than the probabilistic method to calculate Ramsey numbers. “The problem has been to try to defeat this [bound] coming from sampling at random,” Conlon said.

And that is what Conlon and Ferber finally did this fall.

Incorporating Order

The new proof improves the lower bound for Ramsey numbers for three or more colors.

Prior to Conlon and Ferber’s work, the lower bound for three colors was ($latex \sqrt{3}$)^t (approximately 1.73^t). They improved that bound to 1.834^t. For four colors, they raised the lower bound from 2^t to 2.135^t. Both are gigantic leaps. By increasing the base number being raised to the power t, Conlon and Ferber proved that there exist exponentially larger three- and four-colored graphs that lack the requisite monochromatic cliques. In other words, they showed that disorder can persist within larger graphs than previously known.

Conlon and Ferber’s goal was to color a complete graph without creating large monochromatic cliques. To do that, they figured out a way to efficiently distribute one color (red) according to a fixed rule before applying the remaining colors at random. This hybrid method afforded them additional control over the graph structure that Erdős didn’t have.

For the fixed part of the plan, they placed the vertices in a special kind of geometric space, so that each vertex was defined by a set of coordinates. Then they decided which edges to color red via a two-step process.

First, they took the coordinates of each vertex, squared them and added them together — a process known as taking the sum of squares. Due to the nature of this particular geometric space, this sum-of-squares operation produced one of two values: 0 or 1. Next, focusing only on the vertices whose sum of squares was 0, they calculated the “inner product” between pairs of vertices — a standard operation in linear algebra. If an edge connected a pair whose inner product was a certain value, they colored it red. This accounted for half the total edges.

After completing this deterministic part of their approach, Conlon and Ferber moved on to the random part. For the remaining edges they flipped a coin — just as Erdős would have — to determine whether to color a given edge blue or green.

This approach turned out to be a great way to avoid forming monochromatic cliques as the size of a graph grows. That was by design: The pair engineered the deterministic step to generate red edges that were spread out over the whole graph. At a distance they’d look almost as if they’d been scattered at random — and indeed, Conlon and Ferber refer to this arrangement of red edges as “pseudo-random.”

This pseudo-random distribution of red edges achieves two desirable things. First, by spreading out the red edges, it ensures that you don’t end up with any large red cliques (which is what you’re trying to avoid if you want to increase the lower bound). Second, the widespread red edges break up the graph, leaving fewer wide-open spaces that could end up getting filled in randomly by monochromatic cliques of another color.

“We wanted to make sure that the first color, which we used deterministically, reduced the number of potential cliques,” Ferber said.

Mathematicians reacted to the new proof quickly. Within days of its release, Wigderson posted a follow-up paper that used their methods to prove an even slightly better lower bound for Ramsey numbers for four or more colors. After decades of stasis on Ramsey numbers, the dam had finally broken.

“Our state of knowledge has been stuck since Erdős in the ’40s, so anything that provides a new approach to questions of this type is exciting,” Wigderson said.

Correction: November 9, 2020

Some versions of our diagram on “The Erdős Method” described a graph with 0 vertices; it should be 10 vertices. All versions are now correct.