David Conlon and Asaf Ferber raised the lower bound for the values of the multicolor Ramsey numbers. These numbers indicate how much you can increase the graph until the inevitable patterns begin to appear in it.
Some of the most stubborn numbers in mathematics, after more than 70 years of resistance, are finally beginning to give in.
In a four-page proof, published in September, David Conlon and Asaph Ferber gave the most accurate estimate of the "multicolored Ramsey numbers." These numbers describe the size of the graphs to which they can grow before certain patterns inevitably begin to appear in them.
“There are no absolute coincidences in our universe,” said Maria Aksenovich of the Karlsruhe Institute of Technology in Germany. "There are always clusters of order somewhere, and Ramsey numbers quantify it."
Graphs are collections of points (vertices) connected by lines (edges). Mathematicians are especially interested in the question of how many vertices and edges can be added to a graph before various substructures begin to appear in it.
“If your graph is large enough, a significant portion of it will be well-ordered,” said Maria Chudnovsky of Princeton University. "Beauty is difficult to explain in words, but this phenomenon is considered to be beautiful."
Ramsey numbers refer to a specific sequence, a monochrome click. This is a set of vertices that will be connected to each other by edges of the same color after a certain coloring procedure.
Asaf Ferber of the University of California, Irvine
Ramsey numbers differ depending on the size of the desired clique and the number of colors in which you color the graph. Most of the Ramsey numbers cannot be calculated by mathematicians, since almost all but the simplest graphs are too difficult to analyze directly.
The best that mathematicians are usually capable of is to specify a range of possible values for Ramsey numbers. As if you wanted to find out where your friend is at the moment, but all that you were able to establish was that he is somewhere south of Moscow and north of Sochi.
The new proof makes it possible to determine the range of values of the Ramsey numbers much more accurately than any result since Pal Erdos first began to study these numbers.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 the multicolor Ramsey numbers. It turned out to be exponentially more accurate than the best of the previous estimates. Their result gives mathematicians a new way to understand the extremely important scheme for the interaction of order and randomness in graphs.
“This is an amazing result,” Aksenovich said. "I liked him very much."
Colored links
The essence of the Ramsey numbers, invented by the British universalist Frank Ramsay in the 1920s, is easiest to understand with an example. Let's start with a graph with five vertices. We connect each vertex with all the others - we get, as mathematicians say, a complete graph. Is it possible to color all the edges blue or red so that the graph does not contain three vertices connected to each other in pairs by edges of the same color? In this case, yes.
But if we start with a complete graph of six vertices, we cannot paint its edges with two colors without generating a monochrome clique of three or more vertices. In other words, for two colors and a clique size of 3, the Ramsey number will be 6 (the graph must have at least 6 vertices).
Ramsey numbers change depending on the number of colors and the size of the desired monochrome clique. But in general they are difficult to calculate - exact values are known to mathematicians only in a small number of cases. Even for small clicks of 5 and two colors, it is better what mathematicians can say about the Ramsey number - that it is in the range of 43 to 48.
“An embarrassing situation,” said Yuval Wigderson , a graduate student at Stanford. "We have been working on this task for almost 100 years and have not learned anything."
Connect the five vertices to form a complete graph. Such a graph can be colored with two colors so that three vertices do not appear, connected by edges of the same color.
But by going to a graph of six vertices, it is already impossible to avoid the appearance of three such vertices.
Ramsey numbers are difficult to calculate because the complexity of the graph grows rapidly with the number of vertices. For a graph of six vertices and two colors, all the options can be enumerated manually. For a graph of 40 vertices, there are 2,780 ways to color the edges in two colors.
“We have to check too much,” Aksenovich said.
The mathematicians who study Ramsey numbers have a story that is usually credited with Erds. She describes how quickly these calculations get too complex. Imagine that aliens invaded the Earth. They offer to spare our planet if we can give the correct values for the Ramsey numbers. If they ask us to name the Ramsey number for the case with two colors and cliques of size 5, we will need to throw all the resources of humanity to solve this problem. If they ask us to calculate the Ramsey number for cliques of size 6, it will be easier for us to immediately prepare for battle.
“If they ask us for the Ramsey number for [click size] 6, then it’s better to attack right away,” Aksenovich said.
Studying randomness
Since it is largely impossible to calculate the exact meaning of Ramsey numbers, mathematicians instead prefer to gradually limit their values. They prove that a number is greater than a certain lower limit, and less than an upper limit. The new work improves this accuracy for the lower limits, but says nothing about the upper ones.
In 1935, Pal Erdos and Gyorgy Szekeres established the first such border. They used a short proof that the Ramsey numbers for two colors must be less than 4 t , where t is the size of the monochrome clique you are interested in. They also found that the Ramsey numbers for the three colors should be less than 27 t . 10 years later, in 1947, Erdos calculated the first lower bound for these numbers: for two colors it is (√2) tvertices, and for three - (√3) t .
There is a big difference between (√2) t and 4 t , especially at very large t values. This gap reflects the fuzzy understanding of Ramsey numbers by mathematicians. However, the shape of the borders - how the size of the desired graph is expressed in terms of the size of the desired clique - hints at what mathematicians are most interested in.
“What I would love to understand is how these Ramsey numbers grow with the size of the clique,” said Lisa Sowerman , a postdoc at the Institute for Advanced Study in Princeton.
Therefore, Erds' longest-lived contribution to the study of Ramsey numbers was not the boundaries themselves, but the method of calculating them. This is how he calculated the lower bound.
Imagine you have a complete graph with 10 vertices and 45 edges. Imagine that you need to find out if it is possible to color the edges with three colors without creating a monochrome clique of a certain size - let's say 5 (5 vertices connected by 10 edges).
You can start, as Erdös did, by randomly painting the edges. For each edge, let's roll something like a three-sided dice and paint it with the color that comes up randomly. Erdos knew that it was easy to calculate the probability that any subset of 10 edges would end up being the same color. You just need to multiply the probability that one of the edges will be, say, red, with the probability that the other edge will be red, and so on for all ten edges (that is, 1/3 10). Then he multiplied that number by three to account for the fact that any of three different colors can generate the desired monochrome clique.
Then Erdos looked at the total number of different clicks from the five vertices in the graph. There can be 252 of them. Finally, he took the probability that one of them will produce a monochrome clique and added it to the probabilities that any of the remaining 251 vertices will produce such a clique. This is the so-called. calculation of the "join boundary", which gives the probability of obtaining a monochrome clique when randomly coloring the edges.
As long as the join boundary remains less than 1, you know that the random coloring method does not guarantee a given monochrome clique. In our example, the border is 0.0128. This is very far from the guaranteed appearance of a monochrome clique of 5 vertices, which means that for this example the Ramsey number is more than 10 vertices.
Mathematicians call this approach the probabilistic method. This is an ingenious workaround for solving difficult problems. Instead of looking for examples of colorings that do not contain monochrome cliques of various sizes, Erds simply proved that such non-clickable colorings should exist (since the union boundary is less than 1). That is, the Ramsey number must be greater than the number of vertices in the graph that we color randomly.
Pal Erdos invented the "probabilistic" method for calculating Ramsey numbers.
1) We start with a complete graph of 10 vertices. When coloring the edges with three colors, is it always possible to find 5 vertices connected by 10 edges of the same color?
2) The probability that a particular edge is red (and not blue or yellow) is 1/3
3) The probability that 10 edges are red is (1/3) 10
4) In total, three colors can generate a monochrome clique.
5) The total number of different clicks from 5 vertices is 252.
(1/3) 10 * 3 * 252 = 0.0128 - the probability of getting a monochrome click when randomly coloring the edges.
“We can prove the existence of something without showing it directly,” Wigderson said.
In the next 70 years, mathematicians improved the lower bound of Erds for two and three colors only once - in 1975, it was incrementally improved by Joel Spencer. Many have worked on this problem, but no one has found a better way to calculate Ramsey numbers than the probabilistic method. “The problem was trying to get around this [limitation] due to random sampling,” Conlon said.
This is exactly what Conlon and Ferber managed to do this fall.
Enabling order
The new proof improves the lower bound for Ramsey numbers for three or more colors.
Prior to this work, the lower bound for three colors was (√3) t (approximately 1.73 t ). Conlon and Ferber improved it to 1,834 t . For four colors, they raised the lower limit from 2 t to 2.135 t . Both of these results are giant steps forward. By increasing the base to the power t, Conlon and Ferber proved the existence of exponentially large three- and four-color graphs that do not have monochrome cliques. In other words, they showed that disorder occurs in larger graphs than previously thought.
Conlon and Ferber's goal was to colorize the complete graph without generating large monochrome cliques. They came up with a way to effectively distribute one color (say, red) according to a fixed rule before applying all the other colors at random. This hybrid method gave them control over the graph structure that Erds did not have.
David Conlon of the California Institute of Technology The
Fixed Rule meant the distribution of vertices in a specific geometric space, in which each of the vertices was defined by a set of coordinates. They then followed a two-step process when deciding which edges to paint red.
First, they took the coordinates of each vertex, squared them, and added them to get the sum of the squares. Because of the peculiarity of this geometric space, the sum of squares gave one of two values, 0 or 1. Then they left only those vertices whose sum was 0, and calculated the dot product of pairs of vertices (a standard operation for linear algebra). Then they painted an edge red if it connected a pair of vertices whose dot product was equal to a certain value.
After completing the deterministic part of the algorithm, Conlon and Ferber moved on to the random one. For all the other edges, they flipped a coin - as Erds would do - to determine if it would be green or blue.
This approach has proven to be a great way to avoid monochrome clicks as the graph grows. And that was by design: the couple specially designed the deterministic stage so that the red edges are evenly distributed throughout the graph. At first glance, they looked like they were distributed randomly. Indeed, Conlon and Ferber call this edge coloring "pseudo-random."
The pseudo-random distribution of red edges achieves two goals. First, by scattering red edges all over the graph, we ensure that no big red clicks appear in it (which is what we are trying to avoid by wanting to increase the bottom border). Second, the red edges scattered throughout the graph break it apart, leaving fewer empty spaces that could accidentally be filled with monochrome clicks of a different color.
“We wanted to make sure that the first color we used deterministically reduced potential clicks,” Ferber said.
Mathematicians reacted quickly to the new proof. A few days after the release, Wigderson published a work following this , where their method was used to increase the lower bound of the Ramsey numbers for the case with four or more colors. After decades of immobility, the Ramsey numbers dam was finally broken.
“Our knowledge on this topic has not changed since the 40s, since the time of Erdos. Therefore, anything that gives us a new approach to this type of issue is of great interest, ”said Wigderson.