Mathematicians have found a new way to impose order on chaos in the form of an answer to a challenge which has puzzled them for nearly a century – a so-called Ramsey problem known as r(4,t).
In mathematics, Ramsey theory deals with the ‘order in disorder’. No matter how complex a large system is, order will emerge as a smaller subsystem with unique structure.
Humans are pattern-seeking creatures living in a world of random chaos. We look for order in everything, from our lives, the world around us, to the Universe, and you could say Ramsey theory explains our ability to find it.
Ramsey numbers can be thought of as representing the boundaries of disorder. And it’s notoriously hard to figure them out.
Since mathematician Frank Ramsey proved Ramsey’s Theorem in the late 1920s, there’s been perplexion on the specific problem that Sam Mattheus and Jacques Verstraete of the University of California, San Diego, finally cracked.
“Many people have thought about r(4,t) – it’s been an open problem for over 90 years,” Verstraete says.
“It really did take us years to solve. And there were many times where we were stuck and wondered if we’d be able to solve it at all.”
A common analogy for Ramsey theory requires us to consider how many people to invite to a party so that at least three people will either already be acquainted with each other or at least three people will be total strangers to each other.
Here, the Ramsey number, r, is the minimum number of people needed at the party so that either s people know each other or t people don’t know each other. This can be written as r(s,t), and we know the answer to r(3,3) = 6.
“It’s a fact of nature, an absolute truth. It doesn’t matter what the situation is or which six people you pick – you will find three people who all know each other or three people who all don’t know each other,” Verstraete says.
“You may be able to find more, but you are guaranteed that there will be at least three in one clique or the other.”
Ramsey problems are traditionally solved using random graphs. For example, with s plotted as points with blue lines between them and t as points with red lines. If a graph is large enough you’ll find order, but it gets complicated quickly.
Mathematicians demonstrated in the 1930s mathematicians demonstrated a theorem in the 1930s that would later indicate the answer to r(4, 4) is 18. And since 1995 we’ve known r(4,5) = 25. So cap your guest list at 24 if you want to keep a possibility of not inviting either four acquaintances or five strangers.
We’re not sure if there are implications to four acquaintances catching up or bringing together five strangers to swap stories. But if you invite 25 people to a party, Ramsey theory says you can be certain one of those will happen.
Party dynamics aside, finding the Ramsey number for a problem essentially means figuring out the fewest elements a system needs to have to be sure of a certain property.
It’s useful in computer science and mathematics to structure communication networks, and create fraud detection algorithms, among other things.
“Because these numbers are so notoriously difficult to find, mathematicians look for estimations,” Verstraete explains. “How do we find not the exact answer, but the best estimates for what these Ramsey numbers might be?”
After discovering the estimations could be tightened using pseudorandom graphs, Verstraete and University of Illinois-Chicago mathematician Dhruv Mubayi successfully solved r(3,t) in 2019.
But Verstraete struggled to create a pseudorandom graph for r(4,t), so he and Mattheus tackled the longstanding problem by combining the field of finite geometry with graph theory.
With the help of a Hermitian unital used in finite geometry, the researchers fixed s (mutual acquaintances) at 4 and studied the Ramsey number as t (strangers) increased.
After almost a year and several math obstacles, they found r(4,t) is close to a cubic function of t. For a party with four people who all know each other or t people who don’t, you need t3 people.
As the researchers state, this is a best estimate, but t3 is very close to the exact answer. If you’re interested, their result can be expressed mathematically as:
r(4,t) = Ω(t3/log4t ) as t → ∞
The team believes their approach will be useful for other Ramsey numbers and could aid in the estimation of other mathematical functions.
“One should never give up, no matter how long it takes,” Verstraete says. “If you find that the problem is hard and you’re stuck, that means it’s a good problem.”
A preprint of the study is available on arXiv, and it’s currently being reviewed by the journal Annals of Mathematics.
