Calculating Ramsey numbers is so difficult that one mathematician once said he’d rather fight off an alien invasion. Now, mathematicians have made the first major advance in nearly a century.
The key to a successful party is a good mix of people
Mathematicians have made a breakthrough on an incredibly difficult problem in combinatorics, the study of combinations. It is the first significant advance in nearly a century for our understanding of Ramsey numbers, which can be used to describe the minimum size of a party where cliques of a certain size can or can’t exist.
Named after mathematician Frank Ramsey, these numbers deal with the possible relationships between nodes on a mathematical network called a graph, which are a major object of study in maths. The numbers, first discovered in 1928, can be described in terms of people at a party.
Suppose you are hosting a party and want to make sure there is a good balance between people who know each other and those who don’t. Too many mutual acquaintances will form a clique, excluding the others at the party, while too few risks an anti-clique, plagued by awkward small talk.
The question, then, is whether there is a minimum party size that will always produce a clique or anti-clique of a certain size. This is the Ramsey number. For instance, the Ramsey number for a clique of three is six, because in a six-person party you can always find either a clique of three people who know each other, or who don’t.
While this is simple for small numbers, like three, it rapidly becomes very difficult to calculate for larger numbers as the possible combinations grow. It has long been a goal for mathematicians to find a general solution for any Ramsey number.
Paul Erdős, who in 1935 found that the upper limit for any Ramsey number is 4 to the power of the clique size, once said that finding the exact Ramsey number for a clique of six was so difficult that if aliens asked us to try to calculate it, or be destroyed, we would have no choice but to try to attack them first. Since then, generations of mathematicians have tried to significantly improve upon Erdős’s limit, but without much success.
Now, Julian Sahasrabudhe at the University of Cambridge and his colleagues have shown the upper limit for Ramsey numbers can be reduced from 4 to the power of the clique size to 3.993 to the power of the clique size.
“From the outside, it seems sort of silly — like, OK, mathematicians are just trying to improve some number and who cares?” says Sahasrabudhe. “But what’s interesting about these quantitative changes, like the difference between the Erdős bound and previous bounds and our work, is there’s really some quantitative improvement that reflects a deepening of our understanding of the [mathematical] structures.”
Sahasrabudhe and his colleagues first started working on the problem in 2018, at the National Institute for Pure and Applied Mathematics in Rio de Janeiro, Brazil. “It’s a famous problem and we wanted to be ambitious and had some ideas — and it seemed like it was actually going pretty well, which was exciting,” says Sahasrabudhe.
In the first few months the team had sketched out a rough plan of what the proof could look like, he says, but quickly ran into an obstacle, which involved calculating how points clumped together on high-dimensional spheres.
After trying to solve this problem for years and failing, Sahasrabudhe and his team realised they could reformulate their proof to avoid the sphere question entirely, after which things rapidly progressed. “Instead of going over the mountain, we realised we could actually somehow sneak around it,” he says.
The final proof, which is more than 50 pages long and yet to be formally verified, uses elements of Erdős’s original proof, which involved zooming into particular people in arbitrarily large parties and working out the probabilities of their relationships to their neighbours, and also identifying adjacent structures to cliques called “books”, which are easier to find but guarantee that cliques exist.
“For at least the last 50 years, every eminent person in my field has tried quite hard to improve these bounds and failed,” says David Conlon at the California Institute of Technology. “The fact that they have now improved this result is a big deal.”
Now that the barrier of 4 has been broken, other researchers can now use and optimise Sahasrabudhe and his team’s methods to get the number slightly lower than 3.993. “This is a fiendishly hard problem,” says Peter Cameron at the University of St Andrews, UK. “A tiny little improvement like this represents a huge breakthrough in techniques for attacking it.”
For more such insights, log into www.international-maths-challenge.com.
*Credit for article given to Alex Wilkins*