After a century of mathematical contemplation, a team of mathematicians at the University of California (UC) San Diego has successfully cracked a challenging problem in Ramsey theory. This feat marks a significant breakthrough in a field that has seen little progress since the legendary Paul Erdös made some pioneering contributions in 1937.
Ramsey theory, a complex branch of mathematics named after British mathematician and philosopher Frank P. Ramsey, often finds its most accessible description in the context of a party. The most famous problem in this field, known as r(3,3) or the “theorem on friends and strangers,” seeks to determine if, in a group of six people, there will always be at least three individuals who all know each other or three who are complete strangers. The answer to r(3,3) has now been definitively established as six, meaning that in any such gathering of six people, you will inevitably find three individuals who belong to the same clique or three who do not know each other.
Once mathematicians resolved the r(3,3) problem, they began pursuing solutions for more intricate challenges, such as r(4,4), r(5,5), and r(4,t), where the number of unconnected points varies. Paul Erdös and George Szekeres had previously determined that r(4,4) equates to 18, but r(5,5) remains a tantalizing mystery in the world of mathematics.
The pursuit of r(4,t) had persisted as an unsolved problem for over 90 years. “Many people have thought about r(4,t) – it’s been an open problem for over 90 years,” said Jacques Verstraete, one of the mathematicians behind the recent breakthrough. The quest for an answer was characterized by the challenge of dealing with vast numbers of potential graphs. Finding exact solutions was difficult, so mathematicians often sought estimations to narrow down the possibilities.
Verstraete’s journey into r(4,t) began when he read about the problem in a book by UC San Diego professors Fan Chung and Ron Graham. This conjecture by Erdös came with a reward of $250 for the first person to solve it, a considerably more substantial sum in the 1930s. While Verstraete initially had the problem in the back of his mind, it was only after a breakthrough in pseudorandom graphs, made while working on a different problem with mathematician Dhruv Mubayi, that he started to make progress.
In 2019, he and Mubayi managed to solve r(3,t), but the breakthrough in r(4,t) came about after Verstraete teamed up with Sam Mattheus, who brought his expertise in finite geometry to the table. It took almost a year of collaborative work, but they eventually discovered that a party where there are always four individuals who know each other or t individuals who do not know each other would require approximately t^3 people present, where t is a variable (hence the approximation).
The mathematicians emphasized the perseverance and determination required to tackle challenging problems like these, echoing the sentiment that a good problem in mathematics always “fights back.” As their research awaits peer review and acceptance, the tantalizing mystery of r(5,5) might remain on their whiteboard, continuing the legacy of mathematical exploration and discovery.