A new math formula answers a long-standing party problem

If you invite six people to a party, either at least three of them will all know each other, or at least three will have never met before. But how many people do you need to invite to make sure a certain number of them are all friends or all strangers?

It’s a long-standing problem in combinatorics, the branch of mathematics that counts the ways in which a set of objects can be arranged. The optimal answer is surprisingly difficult and unknown except for a few simple cases. But a team of four mathematicians has now found the best upper bound yet – and the most substantial improvement over a previous solution from 1935.

“All combinatorics have tried to answer this question, and I think it’s fair to say that it’s one of the two or three main open problems in extreme combinatorics, or maybe even the real top” , tweeted mathematician Tim Gowers from the University of Cambridge, UK.

Gowers’ remark followed a seminar in Cambridge on March 16 given by his colleague in the department Julian Sahasrabudhe. In a coordinated revelation, two of Sahasrabudhe’s three colleagues – Robert Morris of the Institute of Pure and Applied Mathematics (IMPA) in Rio de Janeiro, Brazil, his doctoral student Marcelo Campos and Simon Griffiths of the Pontifical Catholic University (PUC) neighbor – also described their results at seminars at IMPA and in São Paulo, Brazil, on the same day. Otherwise, the book has so far only been presented in a 57-page preprint.¹ which has not been peer reviewed.

Party people

The party problem was first stated in 1930 by British mathematician and logician Frank Ramsey. One way to express it is to imagine a number R of people gathered in a room, each being either a friend or a stranger to the others. Suppose you are looking for a size group k who are all friends or all strangers. For a given kwhat is the smallest R(k) who is guaranteed to satisfy this condition? It has long been known that any group of 6 people contains at least 3 friends or 3 common strangers, and that any group of 18 people contains at least 4 friends or 4 strangers. But already for the number 5, the exact solution R(5) is unknown, except that it must be between 43 and 48.

The problem can be mapped onto the mathematical theory of networks, the abstract objects made up of nodes and links connecting them. Each node will represent one person at the party, and two people are connected by a link, which is color coded – red if two people know each other, and blue if they don’t. The question then becomes, how big does a network need to be to guarantee that it contains at least one all-blue subset or one all-red subset of a certain size?

Mathematicians Paul Erdős and George Szekeres showed in 1935 that R(k) is at most 4^k. This bound is far from optimal: for example, for k = 4, it gives 4⁴ = 256, whereas we know that 18 would suffice. But the formula gives at least an upper bound valid for any k.

The question that has plagued combinatorics since then is whether this upper bound can be smaller — whether it is possible to show that there exists a bound VS^k for which C is less than 4. Even lowering it by a tiny amount, says Sahasrabudhe, “would be an exponential improvement over what was known [previously]”, which means that the revision of the terminals on VS is the best possible way to improve on previous results.

The four researchers have now shown that the upper bound can be reduced to at least (3.9995)^k. The result could have important ramifications for other areas of mathematics – in particular, for the study of networks that have a random element, which can arise in real-world problems ranging from epidemiology to optimization problems and planning, as well as for number theory and geometry.

Books and networks

The collaboration of the four researchers began in 2018, when Sahasrabudhe visited IMPA. Inspired by work on Ramsey’s theorem by combinatorics David Conlon at the California Institute of Technology in Pasadena, the team was able to fairly quickly sketch out an outline of what a proof might look like. “It turned out to be just the start of a long journey,” says Sahasrabudhe.

Conlon’s work suggested an approach involving auxiliary networks known as “books”. The researchers set about designing an algorithm to build the books, but the challenge was to rule out “pathological” exceptions to it. It wasn’t until January of this year that they felt confident that they had found a way around the problem. “At the beginning of February, we had a good idea of ​​how we could use these ideas to achieve the exponential improvement,” says Sahasrabudhe. “We were ready to go public in mid-March.”

Their evidence has yet to be verified by others, he warns. “Now that the document is public, the community will enter a period of validation, simplification, assimilation and improvement of our work. It will be exciting to see where others take the ideas.

“The authors used elementary methods in an extremely clever way,” Gowers said. Nature. He expects the result to stand up. “They had a huge incentive to be careful and, I am told, they were indeed extremely careful. All four are incredible mathematicians who have done marvelous work in the past. He adds that Sahasrabudhe’s presentation contained “a very compelling story of what was going on.”

“The evidence was very different from the type of argument I had been trying to find,” adds Gowers, “and I don’t think I would ever have found it.”

“It’s a problem that has proven consistently difficult, despite having been extremely well studied for nearly a century,” says Conlon. “Their progression is a meteoric success.”