24/04/2023

At IMPA, the biggest breakthrough in Ramsey's Theorem is discovered.

Robert Morris (IMPA), Julian Sahasrabudhe (Cambridge), Simon Griffiths (PUC-Rio) e Marcelo Campos (doutor pelo IMPA)

For the past 88 years, researchers worldwide have attempted to advance the upper bound of Ramsey's Theorem, one of the earliest in combinatorics. In January of this year, during the IMPA Summer Program, a group composed of Robert Morris (IMPA), Marcelo Campos (PhD from IMPA), Simon Griffiths (PUC-Rio), and Julian Sahasrabudhe (Cambridge) developed a new algorithm capable of improving the theorem's bound. This advance is the most significant in the field since 1935.

Proposed by the British mathematician Frank Plumpton Ramsey (1903–1930), the theorem seeks to find regularities within a large, chaotic structure. The study of the problem opened new doors for combinatorics, a branch of mathematics that studies the ways in which finite collections of objects can be organized.

“Since this is one of the most famous problems in combinatorics, almost everyone in the field has tried to solve it. And we thought that a very different tool would be needed, or that we needed to understand the 'structure' of coloring to arrive at the answer, but the truth is that the proof is simpler than everyone expected,” said Robert Morris.

Marcelo Campos explained the problem using social networks as an example. Ramsey's Theory states that for any number k, there exists a number R(k) with the following property: if there are R(k) people on Facebook, and any two of them are friends or do not know each other, then it is possible to find k people who are either all friends with each other or all strangers.

“The social network represents what in mathematics we call a graph. For us, what matters is the connection between the points of a graph. We are looking for the type of structure in which all points are interconnected or in which none are connected,” Campos explained.

Finding this structure is not so simple, especially if the coloring – that is, the interconnected pairs – are determined in an “almost” random way.

“This set, which in this example represents the people on the social network, can be thought of in various ways. So, we believe we have an 'adversary' that could adopt a strategy to make this more difficult, to deal with the worst-case scenario. One of the strategies it could adopt is to connect people randomly. In other words, it's as if we flipped a coin and it determined who is a 'friend' or 'not a friend' on Facebook. What we want to prove is that the algorithm finds the structure we are looking for anyway.”

Challenging as it is, the theory has proven to be a vast field and was explored by British mathematician William Timothy Gowers, winner of the Fields Medal in 1998. In a series of tweets , Gowers acknowledged the group's progress.

"Basically all combinatorics researchers have tried hard to answer this question, including myself," he wrote.

The last advance on the upper limit was in 1935.

The problem is interpreted using Graph Theory, where objects – called vertices – are interconnected by edges with blue or red colors. The sets are called "cliques," and the question is: what is the number of vertices needed to guarantee the existence of a clique of a certain size with edges of only one color?

In 1935, Erdős and Szekeres showed a pioneering result and arrived at the upper bound R(k)<4^k through an algorithm. Campos, Griffiths, Morris, and Sahasrabudhe found a new upper bound: (3.995)^k.

“It’s a search for a type of substructure in a graph. We managed to make the first exponential improvement to this work. This algorithm allows us to find the substructure more efficiently – and it works for any graph you want. It will always be possible to find the substructure,” said Campos.

The result may contribute to research by experts in combinatorics and may even lead to developments in other areas.

“In a problem like this, you want to understand the object, so the more proofs the better. Finding different proofs of the same thing can open up paths you never imagined existed. We hope that our work will lead other people to also find different proofs of this theorem. The exchange of ideas enriches mathematics,” said Morris.

Since 2018, the group has been meeting to explore the problem and, after many attempts, it was possible to define the best solution found. The "eureka" moment happened during the IMPA Summer Program , a unique opportunity for mathematicians to meet in person, since Julian Sahasrabudhe is an assistant professor at the University of Cambridge.

Previously, Sahasrabudhe was a distinguished postdoctoral fellow at IMPA (2017-2018), as was Simon Griffiths, also a distinguished postdoctoral fellow at the institute (2010-2013) and current adjunct professor at PUC-Rio. Marcelo Campos was supervised by Robert Morris during his doctoral studies and presented his thesis in March of this year.