Mathematicians Solve Nearly Century-Old Party Problem

SAN DIEGO — In the realm of mathematics, some problems seem deceptively simple but can be fiendishly difficult to solve. Take, for instance, the concept of Ramsey numbers. Imagine you’re at a party with five other guests. Some pairs of people are friends, while other pairs are strangers. The question is: among any group of six people, will there always be at least three mutual friends or three mutual strangers?

The answer, surprisingly, is yes. This is a classic example of a Ramsey number, named after the mathematician Frank Ramsey. More generally, Ramsey numbers, denoted r(s,t), represent the minimum number of people needed at a party to guarantee that there will be either s mutual friends or t mutual strangers.

While the existence of these numbers was proved long ago, actually calculating them has been an immense challenge. Mathematicians have grappled with this problem for decades. But now, two researchers from the University of California San Diego have made a significant breakthrough in solving one of these puzzles.

The problem, known as r(4,t), is part of a branch of mathematics called Ramsey theory. It asks: how many people do you need at a party to guarantee that there will always be either four people who all know each other or a certain number (t) of people who are all strangers to each other?

Jacques Verstraete and Sam Mattheus, the UC San Diego mathematicians behind the new discovery, explain that this seemingly simple question is actually incredibly complex. “It’s a fact of nature, an absolute truth,” Verstraete says in a statement. “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. You may be able to find more, but you are guaranteed that there will be at least three in one clique or the other.”

In mathematical terms, the party problem is represented by a graph – a series of points (the people) and lines between those points (their relationships). Ramsey theory suggests that in a large enough graph, you’ll always find either a set of points with no lines between them (a group of strangers) or a set of points with all possible lines between them (a group of mutual friends, known as a “clique”).

The simplest Ramsey problem, r(3,3), is sometimes called “the theorem on friends and strangers.” It states that in any group of six people, you’ll always find either three mutual friends or three mutual strangers. But what happens when you increase the numbers?

It turns out, the math gets complicated fast. The solution to r(4,4) – the number of people needed to guarantee either a group of four mutual friends or four mutual strangers – is 18. But r(5,5) is still unknown, and if you tried to solve it by brute force, you’d have to consider more than 10^234 possible graphs for just 45 people!

That’s where Verstraete and Mattheus come in. By using a special type of graph called a pseudorandom graph, they were able to narrow down the range of possible answers for r(4,t). “Many people have thought about r(4,t) — it’s been an open problem for over 90 years,” Verstraete said. “But it wasn’t something that was at the forefront of my research. Everybody knows it’s hard and everyone’s tried to figure it out, so unless you have a new idea, you’re not likely to get anywhere.”

The key insight came from combining ideas from different areas of math, including combinatorics, finite geometry, algebra, and probability. Mattheus, a postdoctoral scholar in Verstraete’s group with a background in finite geometry, was instrumental in building the specific pseudorandom graph they needed.

After years of work and many dead ends, Verstraete and Mattheus finally cracked the problem: r(4,t) is approximately t^3. In other words, if you want to guarantee a group of four mutual friends or t mutual strangers, you’ll need roughly t^3 people at your party.

“It really did take us years to solve,” Verstraete stated. “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.”

Their findings, published in Annals of Mathematics, demonstrate the power of persistence in the face of a challenging problem. As Verstraete’s colleague Fan Chung once said, “a good problem fights back. You can’t expect it just to reveal itself.”

These Ramsey numbers may seem like a fun brain teaser, but they have deep connections to fundamental questions in mathematics. Understanding their growth is closely tied to problems in an area called extremal graph theory, which studies how large a graph can be without containing certain substructures. Improved Ramsey numbers often go hand in hand with breakthrough constructions of such extremal graphs.

Moreover, variants of Ramsey numbers appear in contexts like communication network design, as they relate to the robustness and interconnectivity of the network. As our world becomes increasingly linked by sprawling webs of social and technological connections, insight into Ramsey theory can help light the way forward.

The new result on r(4,t) is a significant leap, but there is still much to be discovered. The exact order of growth of r(4,t) remains unknown, concealing a tantalizing problem for the next generation of mathematicians to tackle. And for larger Ramsey numbers like r(5,t) or beyond, even the rough rate of growth is still a mystery.

So the next time you’re at a gathering, take a moment to appreciate the hidden mathematical patterns in the social fabric around you. And if you happen to spot a group of four friends or a cluster of strangers, remember the decades of dedication that went into understanding why they’re there.