Ramsey’s theorem, one of the first in the mathematical field of combinatorics, was formulated and proved by the British Frank Plumpton Ramsey in 1928, having been published only after his death in 1930.

Over the past 88 years, researchers around the world have attempted to overcome the so-called “upper limit” of the problem. The feat was finally achieved by a team during the summer program of the Institute of Pure and Applied Mathematics (IMPA).

The group is made up of the Brazilian Marcelo Campos (IMPA doctor); by the British Robert Morris (IMPA) and Simon Griffiths (assistant professor at the PUC-Rio) and by the Canadian Julian Sahasrabudhe, assistant professor at the University of Cambridge, in England.

Since 2018, scientists have been coming together to explore the problem, but only recently have they come up with a new algorithm that can improve the limit of Ramsey’s theorem. The advance is the largest in the region since 1935.

What does Ramsey’s theory say?

The theory looks for regularities within a large and chaotic structure. This indicates that for any number k, there exists a number R(k) with the following property: if there are R(k) people on Facebook, for example, and two of them are friends or do not know each other not, 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 is called a graph,” explains Campos, in a press release. “For us, what matters is the connection between the points of a graph. We are looking for the type of structure where all points are connected or none are connected”.

Finding this structure is not easy, especially if the coloring – i.e. the interconnected pairs – is “almost” randomly determined.

In this case, it would be like tossing a coin, which randomly determines who is a friend or not on Facebook, compared to Brazilians. “What we want to prove is that the algorithm finds the structure we’re looking for anyway,” he says.

Graph theory

The problem proposed by Ramsey, although applicable in the example of social networks, is generally interpreted from graph theory. This is made up of objects, called vertices, connected by edges of blue or red colors.

Sets are called “cliques” and the question is: how many vertices are needed to guarantee the existence of a clique of a certain size with edges of a single color?

In 1935, mathematicians Paul Erdős and George Szekeres showed a pioneering result and arrived at the upper limit R(k)<4^k through an algorithm. The new team has now found a new result: (3,995)^k.

The discovery can help not only in the field of combinatorics but also in other fields. “We hope that our work will lead others to find different proofs of this theorem as well. The exchange of ideas enriches mathematics,” says Briton Morris.

The group’s progress was hailed by British mathematician William Timothy Gowers, winner of the 1998 Fields Medal, in a series of tweets. He attended a combinatorics seminar at Cambridge, where the discovery of the group was explained by Canadian member Julian Sahasrabudhe.

“Basically, all combinatorics researchers have struggled to answer this question, myself included,” Gowers acknowledged. “I think it’s fair to say that this is one of the top two or three open problems in extreme combinatorics, or maybe even the best.”