A duo of mathematicians at the University of California, San Diego, has found the answer to r(4,t), a long-standing Ramsey problem that has perplexed the math world for decades.
Ramsey problems, such as r(4,5) are simple to state, but as shown in this graph, the possible solutions are nearly endless, making them very difficult to solve. Image credit: Jacques Verstraete / University of California, San Diego.
Ramsey theory is an area of mathematics underpinned by the philosophy that in any large enough structure, there exists a relative large uniform substructure.
The area is named after Frank Plumpton Ramsey, but has roots in a variety of branches of mathematics, including logic, set theory, topology, geometry and number theory.
Celebrated results include Schur’s theorem leading to Fermat’s last theorem modulo primes, Rado’s partition regularity, van der Waerden’s theorem on arithmetic progressions and Shelah’s theorem, and Bourgain’s theorem on Euclidean distortion in metric Ramsey theory, to mention a few.
The area has grown into a cornerstone of modern combinatorics research, and the central quantities of study are known as Ramsey numbers.
The classical expository example is the statement that amongst any six people, there will be at least three people who all know each other, or at least three people who all do not know each other.
“In mathematical parlance, a graph is a series of points and the lines in between those points,” said University of California San Diego mathematicians Jacques Verstraete and Sam Mattheus.
“Ramsey theory suggests that if the graph is large enough, you’re guaranteed to find some kind of order within it — either a set of points with no lines between them or a set of points with all possible lines between them (these sets are called cliques).”
“This is written as r(s,t) where s are the points with lines and t are the points without lines.”
“To those of us who don’t deal in graph theory, the most well-known Ramsey problem, r(3,3), is sometimes called the theorem on friends and strangers and is explained by way of a party: in a group of six people, you will find at least three people who all know each other or three people who all don’t know each other. The answer to r(3,3) is six.”
What happened after mathematicians found that r(3,3) = 6? Naturally, they wanted to know r(4,4), r(5,5), and r(4,t) where the number of points that are not connected is variable.
The solution to r(4,4) is 18 and is proved using a theorem created by Paul Erdös and George Szekeres in the 1930s. Currently, r(5,5) is still unknown.
“Why is something so simple to state so hard to solve? It turns out to be more complicated than it appears,” the researchers said.
“Let’s say you knew the solution to r(5,5) was somewhere between 40-50. If you started with 45 points, there would be more than 10,234 graphs to consider!”
“Because these numbers are so notoriously difficult to find, mathematicians look for estimations.”
About four years ago, Dr. Verstraete was working on a different Ramsey problem with University of Illinois-Chicago mathematician Dhruv Mubayi.
Together they discovered that pseudorandom graphs could advance the current knowledge on these old problems.
In 1937, Paul Erdös discovered that using random graphs could give good lower bounds on Ramsey problems.
What Dr. Verstraete and Dr. Mubayi discovered was that sampling from pseudorandom graphs frequently gives better bounds on Ramsey numbers than random graphs.
These bounds — upper and lower limits on the possible answer — tightened the range of estimations they could make. In other words, they were getting closer to the truth.
In 2019, to the delight of the math world, Dr. Verstraete and Dr. Mubayi used pseudorandom graphs to solve r(3,t).
However, they struggled to build a pseudorandom graph that could help solve r(4,t).
Dr. Verstraete began pulling in different areas of math outside of combinatorics, including finite geometry, algebra and probability.
“It turned out that the pseudorandom graph we needed could be found in finite geometry. Sam was the perfect person to come along and help build what we needed,’ Dr. Verstraete said.
Once they had the pseudorandom graph in place, they still had to puzzle out several pieces of math.
It took almost a year, but eventually they realized they had a solution: r(4,t) is close to a cubic function of t.
If you want a party where there will always be four people who all know each other or t people who all don’t know each other, you will need roughly t3 people present.
There is a small asterisk (actually an o) because, remember, this is an estimate, not an exact answer. But t3 is very close to the exact answer.
“It really did take us years to solve,” Dr. Verstraete said.
“And there were many times where we were stuck and wondered if we’d be able to solve it at all.”
“But one should never give up, no matter how long it takes.”
The team’s paper will be publsihed in the journal Annals of Mathematics.
_____
Sam Mattheus & Jacques Verstraete. 2023. The asymptotics of r(4,t). Annals of Mathematics, in press; arXiv: 2306.04007
