Live Science Plus
Mathematicians make rare breakthrough on notoriously tricky 'Ramsey number' problem
The bounds on Ramsey numbers, which describe relationships between nodes in a network, have been narrowed.
A visual representation of Ramsey theorem for five nodes on a graph. Here, no triangle has edges that are all the same color, indicating no groups of three that are either all 'friends' or all 'strangers.'
Mathematicians have made a breakthrough in one of the thorniest math problems out there — only the third major step forward in 75 years.
The problem involves Ramsey numbers, a deceptively simple concept that is quite slippery, mathematically. A Ramsey number is the minimum size of a group needed to ensure that a certain number of nodes in that group are connected to one another. The most common metaphor is that of a party: How many people do you need to invite to a soiree to ensure that there will be either a group of three that will know each other or a group of three that are complete strangers?
The Ramsey number for 3 is 6. And to ensure that a given party has a group of four friends or four strangers, you'll need to expand the guest list to 18. But the Ramsey number for 5? All mathematicians can say is that it's between 43 and 48. And as the numbers get bigger, the problem becomes increasingly intractable. More nodes in the network mean more possible connections and more possible structures for the resulting graph.
"There are so many possibilities that you can’t even brute-force it," said Marcelo Campos, who co-authored the research as part of his doctoral degree at the Institute of Pure and Applied Mathematics (IMPA) in Brazil.
Famously, mathematician Paul Erdös once said that if aliens landed on Earth and demanded a precise Ramsey number for 5 or they'd destroy the planet, humanity should divert all of its computing resources to figure out the answer. But if they demanded the Ramsey number for 6, humans should prepare for war.
Mathematicians can give a range for any given Ramsey number. In 1935, Erdös figured out that the maximum Ramsey number for a given number N is 4 to the power of N. In 1947, he figured out that the lower bound is the square root of 2 to the power of N. There's a wide range between those upper and lower bounds, though, and researchers have been trying to narrow the gap for decades.
"Basically, the bound has been stuck there," said David Conlon, a professor of mathematics at Caltech who was not involved in the current research.
Get the world’s most fascinating discoveries delivered straight to your inbox.
But now, Campos and his colleagues have made progress on that upper bound: Instead of 4 to the power of N, they can now say that the maximum Ramsey number for a given network is 3.993 to the power of N.
That might not sound like much of a difference, but it's the first step forward on the upper bound since 1935, Campos told Live Science. He and his team pulled off the proof by developing a new algorithm that looks for certain substructures in the graphs of nodes called "books," which then help them find the groups of connected nodes, or "cliques," that they are looking for.
"What they did was find a more efficient way of constructing these books," Conlon told Live Science.
Related stories
Ramsey numbers don't have a specific application in the real world; they're in the realm of pure math. But the quest to pin them down has had real-world impacts. For example, Campos said, in the 1980s, mathematicians explored Ramsey theory with a concept called quasirandomness, which involves groups with certain mathematical properties. Quasirandomness now plays a role in computer science, Campos said.
"Somehow the problem itself has become a very productive one," Conlon said.
The new method may be able to tighten the upper limit even more than Campos and his team showed in their new paper, which they submitted to the preprint database arXiv on March 16. Campos and his team have plans to pursue the method further, and they hope other researchers will build on their work as well.
"I don't think 3.99 is actually going to be the end point," Campos said.
Stephanie Pappas is a contributing writer for Live Science, covering topics ranging from geoscience to archaeology to the human brain and behavior. She was previously a senior writer for Live Science but is now a freelancer based in Denver, Colorado, and regularly contributes to Scientific American and The Monitor, the monthly magazine of the American Psychological Association. Stephanie received a bachelor's degree in psychology from the University of South Carolina and a graduate certificate in science communication from the University of California, Santa Cruz.