Nearly a century after it was first posed, mathematicians have made a breakthrough in one of the most difficult problems in combinatorics – the mind-bending area of math responsible for such concepts as numbers bigger than the universe and completely unique card shuffles.
As any mathematician can tell you, there ain’t no party like a combinatorics party, because a combinatorics party involves decades of painstaking study and intergalactic existential threat. And for proof of that, look no further than the problem of Ramsey numbers – a question traditionally tied to socializing, which one of the most prolific mathematicians in history, Paul Erdős, once warned would spell the end of the human race if some particularly mathematically-minded aliens ever demanded a solution for it.
“Suppose aliens invade the earth and threaten to obliterate it in a year’s time unless human beings can find the Ramsey number for red five and blue five,” he reportedly said of the problem.
“We could marshal the world’s best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.”
Sounds terrifying – but what exactly is this problem that could so imperil the planet? The easiest way to explain it is with a simple example.
Imagine you’re hosting a mixer, and you want to make sure there’s a good balance of guests who know each other and guests who are strangers. What is the minimum number of people you need to invite to ensure there will be at least one group of three who either all know each other or are all strangers?
The answer to that question is known as the Ramsey number for 3 – or if you want to be pedantic, which mathematicians often do, it’s called R(3,3). Figuring it out may sound like a pretty simple task – and in this case, it actually is: the answer is six.
But as is so often the case in combinatorics, things get out of hand pretty quickly: try the same problem for four friends or four strangers, and you’ll need to invite 18 people; try it for groups of five, and you’ll be attempting to solve a problem no mathematician has yet managed to crack.
That’s because, by that point, “there are so many possibilities that you can’t even brute-force it,” Marcelo Campos, who co-authored the new breakthrough as part of his PhD at the Institute of Pure and Applied Mathematics (IMPA) in Brazil, told Live Science. Instead, the best we can do is come up with upper and lower bounds on the solution: the Ramsey number for five is definitely between 43 and 49, but we can’t say more than that for now.
That leads to a natural question: what can we say about the upper and lower bounds for the Ramsey number of some arbitrary value – say, k? Believe it or not, there’s been an answer to this for close to 90 years already, but it’s not a particularly good one: thanks to Paul Erdős and George Szekeres, we know that R(k, k) is at most 4k.
It’s better than nothing, but not by a huge amount: it puts the upper bound for the Ramsey number of 4, for example, at a whopping 256 rather than the 18 we know it to actually be. But ever since this upper bound was proven back in 1935, just seven years after Ramsey numbers were first discovered, nobody has managed to improve on it.
Until now.
“For at least the last 50 years, every eminent person in my field has tried quite hard to improve these bounds and failed,” David Conlon, a professor of mathematics who specializes in combinatorics at the California Institute of Technology, told New Scientist. “The fact that [Campos and his colleagues] have now improved this result is a big deal.”
Now, before we show you the exact result, we should warn you: if you’re not deep into combinatorics yourself, this breakthrough isn’t going to look very impressive. That’s because what Campos and his team have managed to prove is that the upper bound of R(k, k) is not 4k, but about 3.993k – a difference which, on the face of it, we’ll admit looks underwhelming.
But believe us when we say that for those who have dedicated their professional lives to problems like this, it’s an extremely big deal.
“This is a fiendishly hard problem,” Peter Cameron, a math professor at the University of St Andrews who, like Conlon, was not involved in the new paper, told New Scientist. “A tiny little improvement like this represents a huge breakthrough in techniques for attacking it.”
And while Ramsey numbers have no specific real-world applications, the result is exciting even outside the world of pure math. It may be the first major breakthrough in the study of Ramsey numbers for the last 75 years, but the past few decades of study have been far from fruitless. For example, Campos told Live Science, in the 1980s, mathematicians explored Ramsey theory with a concept called quasirandomness – something which has now found use across a range of scientific disciplines.
Even if you’re only in it for the math, though, this may be the start of something pretty amazing. Should the paper hold up to scrutiny – as it stands, it’s not yet been peer-reviewed, but it’s already being scrutinized by those in the field – Campos thinks it’s only a matter of time until the upper bound is improved even further.
“I don’t think 3.99 is actually going to be the end point,” he told Live Science.
The paper is available at arXiv.
Source Link: Rare Breakthrough In Notoriously Hard Math Problem Means Your Parties Just Got More Efficient