University of California (UC) San Diego mathematicians Jacques Verstraete and Sam Mattheus have solved a puzzling Ramsey theory problem that's had little progress since the great Paul Erdös made some breakthroughs in 1937.
Fittingly, the rather complex Ramsey theory – a branch of the numbers game concerned with order within structures, named after British mathematician and philosopher Frank P. Ramsey – is most often described in the context of a party. The best known problem in this graph-theory corner of mathematics, r(3,3), often called the theorem on friends and strangers, supposes that in a group of six people, you’ll find at least three people who all know each other or three who all don’t know each other. The answer to r(3,3), apparently, is six.
"It's a fact of nature, an absolute truth," said Verstraete. "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."
What happened after mathematicians found that the answer to r(3,3) is 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. Erdös and George Szekeres found the answer to r(4,4) was 18 last century. Meanwhile, r(5,5) is still unknown.
"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."
While on face value it may seem not the kind of problem that would take nearly 100 years to figure out, looks are deceiving in graph theory. For example, in solving r(5,5), if you knew the answer was somewhere between 40 and 50, and you started with 45 points on the graph, there would be 10234 graphs to investigate.
"Because these numbers are so notoriously difficult to find, mathematicians look for estimations," Verstraete explained. "This is what Sam and I have achieved in our recent work. ‘How do we find not the exact answer, but the best estimates for what these Ramsey numbers might be?’"
Verstraete first became aware of r(4,t) in Erdös on Graphs: His Legacy of Unsolved Problems, written by UC San Diego professors Fan Chung and the late Ron Graham. The problem is a conjecture from Erdös, who offered US$250 to the first person who could solve it. We imagine the offer of $250 back in the 1930s might have been more 'rewarding' than it is in 2023.
While Verstraete had r(4,t) in the back of his mind for some time, it wasn’t until about four years ago, while working on a different problem with another mathematician, that he made a breakthrough regarding pseudorandom graphs that would set him on the path to solving Ramsey’s puzzler.
In 2019, Verstraete and that mathematician, Dhruv Mubayi, solved r(3,t), but that was as far as they got. It wasn’t until he teamed up with Mattheus, who has a background in finite geometry, that the dream of solving the next problem started to look like it could be a reality.
"It turned out that the pseudorandom graph we needed could be found in finite geometry," Verstraete stated. "Sam was the perfect person to come along and help build what we needed."
It still took almost a year, but the solution to r(4,t) was found: Basically, to have a party where there will always be four people who all know each other or t people who all don’t know each other, it would require approximately t3 people present. (Approximate because it's not precisely three.)
"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."
The mathematicians did not say whether r(5,5) is now up on the whiteboard, as they wait for their research to go through peer review and acceptance in the meantime.
"If you find that the problem is hard and you're stuck, that means it's a good problem,” said Verstraete. “Fan Chung said a good problem fights back. You can't expect it just to reveal itself."
“I got a call from Fan saying she owes me $250,” he added.
Sadly, there was no inflation adjustments for that 1930s finders' fee.
The research is under review in the journal, the Annals of Mathematics.
Source: UC San Diego
