The work is considered a major breakthrough in the search for a solution to Ramsey's theorem, formulated in 1930
Illustration based on Ramsey’s theorem
Vitória Couto / Revista Pesquisa FAPESP
Last March 16, three seminars discussing the same mathematical theorem were delivered almost simultaneously at three different research centers. Having obtained his PhD less than a week prior at the Institute for Pure and Applied Mathematics (IMPA) in Rio de Janeiro, Marcelo Campos of Brazil addressed an audience of about 20 people at the Institute of Mathematics and Statistics of the University of São Paulo (IME-USP). Simon Griffiths, a British professor at the Pontifical Catholic University of Rio de Janeiro (PUC-RJ), gave a presentation at IMPA, while Julian Sahasrabudhe from Canada discussed the topic at the Faculty of Mathematics, University of Cambridge, in the UK.
Later that same day, following the conclusion of the seminars, the trio of mathematicians, along with their British colleague Rob Morris, a researcher at IMPA, jointly uploaded a four-authored paper to arXiv, a repository for preprints, or papers not yet peer-reviewed. A portion of the research community in the field of combinatorics — a branch of mathematics that investigates the extremal, probabilistic, and structural properties of finite objects — had already seen the paper. “Basically all combinatorialists have tried hard to answer this question — including me — and I think it’s fair to say that it is one of the top two or three open problems in extremal combinatorics, or perhaps even the actual top one,” tweeted British mathematician Timothy Gowers — a recipient of the Fields Medal, one of the most prestigious awards in mathematics — a day after he attended the seminar in Cambridge.
As its title suggested, the paper represented an “exponential improvement” on the Ramsey theorem, symbolized by the notation R(k). The theorem itself carries a deceptively simple statement, yet since 1935, there has been little to no substantial progress towards its resolution. “We haven’t actually solved the theorem,” Campos explains. “What we’ve achieved is an algorithm that effectively reduces the upper bound on the solution.”
To a layperson this might appear modest, but what the researchers accomplished received global acclamation as a significant feat, with their paper receiving extensive coverage in science magazines and in the broader media. “I was floored” on learning about the paper, remarked mathematician Yuval Wigderson from Tel Aviv University, in an interview with Quanta Magazine. “I was literally shaking for half an hour to an hour.” Guilherme Mota, a researcher from IME-USP who organized the seminar given by Campos at the São Paulo university, was also surprised by the contributions of his colleagues. “Every expert in combinatorics has tackled this theorem at some point,” says Mota, who also works in the field and has collaborated with two of the four authors of the new paper. “After such a long time without major breakthroughs, it was unexpected.”
Formulated in 1930 by British mathematician Frank Plumpton Ramsey (1903–1930), the theorem that bears his name is as easy to understand as it is difficult to solve as the integer value in its formula increases. A popular adaptation of its formal statement poses the question in everyday terms: what is the minimum number of guests a party must have to ensure there are at least a given number of mutual acquaintances or at least the same number of mutual strangers? It is not necessary that both conditions are satisfied. This mysterious number of guests is represented generically by the letter k in the Ramsey theorem, denoted as R(k). In this example, it is assumed that the relationship of acquaintance or nonacquaintance is reciprocal: if one person is another person’s acquaintance, then the latter is also the former’s acquaintance.
Rodrigo Cunha / Revista Pesquisa FAPESP
As long as k is a low number, the theorem is easily solvable. If k is 2, the answer to the problem is also 2. In a party with a pair of participants, the two guests are necessarily either acquaintances or strangers. There is no third possibility. If k is 3, the theorem can also be solved. The answer is 6. It takes a bit more effort, but even a layperson can understand and demonstrate that with just six guests, there will always be three who know each other or three who do not. For k equal to 4, 18 guests are required.
For a k value of 5 and beyond, mathematicians do not have a definitive answer to the theorem. They can only state that, in this case, the minimum number of guests falls within a range between 43 and 48 people. Thus, as the value of k increases, all combinatorics experts can assert is that the answer to the problem lies between a lower bound (in the previous example, the number 43) and an upper bound (48).
Two different formulas are used to calculate each bound in the partial solution to the theorem. However, both are still far from precise and leave room for optimization. In other words, the equation for the lower bound gives a result much smaller, and the equation for the upper bound gives a result much larger, than the unknown precise answer to the problem. Campos, Morris, Griffiths, and Sahasrabudhe developed an algorithm that significantly improved the formula used to calculate the upper bound. Instead of being 4 raised to the power of k (4k), their new paper shows that the equation could be reduced to 3.995 raised to the power of k (3.995k). The difference may seem subtle, but since 1935, when Hungarian mathematicians Paul Erdös (1913–1996) and George Szekeres (1911–2005) arrived at the formula 4k, no substantial improvement had been made to the equation.
“We used a mathematical trick and got lucky,” Griffiths humorously noted about the group’s approach to improving the upper bound formula. “In this initial paper, which we plan to publish soon in a journal, we haven’t fully exhausted our method. We believe there is still potential to further reduce the value of 3.995 in our equation.”
The group decided to work on Ramsey’s theorem in 2018 when Sahasrabudhe, the Canadian researcher who is now a professor at the University of Cambridge, was nearing the end of his postdoctoral studies at IMPA. “We are always on the lookout for interesting and challenging problems,” says Morris from IMPA. “Our usual approach is to spend a few days discussing a new problem in front of the blackboard, brainstorming ideas, and sketching out the main obstacles. Then we decide if we have an approach worth pursuing further.” The group held most of their meetings in Rio during the summer, when Sahasrabudhe could join them from the UK. During the pandemic, they switched from face-to-face to online meetings.
Rodrigo Cunha / Revista Pesquisa FAPESP
Although they had been considering potential approaches to solving the theorem for around five years, the breakthrough came in January 2023 when they opted for a change of strategy. Once they found the most promising pathway, they arrived at their solution in a matter of days and promptly wrote the paper reporting on their discovery. “We opted for a probabilistic approach to solving nonrandom problems, drawing on the works of Erdös,” says Campos, who joined the group in 2021.
Ramsey’s theorem may not be directly applicable in everyday life, but it has had and continues to have a significant impact on mathematics and related fields. Determining or estimating Ramsey numbers is one of the central problems in combinatorics, with implications in disciplines such as computer science, logic, and statistical physics. Graph theory, a fundamental branch of combinatorics, is closely connected with the theorem.
A graph serves as an abstract representation of a set of elements and the pairwise relationships between elements within that structure. The elements are referred to as nodes, while the relationships between them are represented by lines, or edges, connecting pairs of elements. In the social analogy used to explain Ramsey’s theorem, the graph representing the party consists of nodes (one for each guest) and edges (representing the relationship between each pair of guests, indicating whether they are mutual acquaintances or strangers). Edges connecting two acquaintances are typically depicted in blue by convention, while edges connecting two strangers are often colored red. The underlying concept of Ramsey’s theorem is that within any structure comprising a set of elements, however large and random, there is always a subset of those elements — a smaller structure — that exhibits a certain degree of order.
“Even amidst chaos, there is a trace of organization,” explains Mota. Essentially, the solution to the problem reveals the minimum size that this chaotic structure must have in order for there to consistently exist a substructure with some form of pattern.
Revisiting the party example is helpful to clarify this central point. How many people, acquaintances or strangers, must there be in the set of party guests — an essentially chaotic structure — so that there always exists a group of k mutual acquaintances or a group of k mutual strangers? Both of these groups are a substructure with an inherent order.
“The significance of studying Ramsey’s theorem is that we don’t know much organization may be “hidden” within a structure that, in other respects, seems random,” says Morris. “This is a fundamental question in the study of large finite objects. Investigating Ramsey’s theorem could lead to the development of a toolset that can be applied in a wide range of contexts.”
A Prodigy from Cambridge British mathematician Frank Plumpton Ramsey formulated the theorem that bears his name at the age of 26, shortly before his death
J. M. Keynes Papers Archive / Wikimedia CommonsFrank Plumpton RamseyJ. M. Keynes Papers Archive / Wikimedia Commons
Ramsey’s theorem is arguably the best-known scientific contribution of British mathematician Frank Plumpton Ramsey (1903–1930), who was regarded as a genius by his contemporaries. His work spanned the fields of mathematics, philosophy, and economics. Born in Cambridge, Ramsey was the son of a suffragette and a mathematics professor at Magdalene College, one of 31 colleges forming Cambridge University. He enrolled in higher education at the age of 17. In 1920 he gained admission to Trinity College, another renowned college in Cambridge, and graduated in 1923 as the top student in his mathematics class.
Proficient in German, during his second year of college, Ramsey began translating the book Tractatus logico-philosophicus by Austrian philosopher Ludwig Wittgenstein (1889–1951) into English. Wittgenstein was one of the members of the influential Vienna Circle, a group of philosophers, mathematicians, and thinkers who regularly met in the Austrian capital during the 1920s to debate language and scientific methodology. Ramsey visited Vienna in 1923 and spent six months there the following year, during which he had the opportunity to meet Wittgenstein and other members of the circle.
He published the ideas behind his theorem (and which form the basis of graph theory) in 1930, the year of his untimely death, just before he turned 27. Ramsey died of mysterious causes after an emergency surgery, possibly due to kidney failure, jaundice, or leptospirosis.
This article may be republished online under the CC-BY-NC-ND Creative Commons license. The Pesquisa FAPESP Digital Content Republishing Policy, specified here, must be followed. In summary, the text must not be edited and the author(s) and source (Pesquisa FAPESP) must be credited. Using the HTML button will ensure that these standards are followed. If reproducing only the text, please consult the Digital Republishing Policy.
