Disorder Persists in Larger Graphs, New Math Proof Finds
https://www.quantamagazine.org/new-math-...-20201104/
INTRO: 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.” (MORE)
https://www.quantamagazine.org/new-math-...-20201104/
INTRO: 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.” (MORE)