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 have to invite to make sure that any given number of them are all friends, or all strangers?
This is 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 hard, and unknown except for a few simple cases. But a team of four mathematicians has now found the best upper limit so far — and the most substantial improvement to a previous solution dating back to 1935.
“All combinatorialists have tried hard to answer this question, 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 mathematician Tim Gowers of the University of Cambridge, UK.
Gowers’ remark followed a seminar in Cambridge on 16 March given by his departmental colleague Julian Sahasrabudhe. In a coordinated reveal, two of Sahasrabudhe’s three coworkers — 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 nearby Catholic Pontifical University (PUC) — also described their result at seminars at IMPA and in São Paulo, Brazil, on the same day. Otherwise, the work has so far been presented only in a 57-page preprint1 that has not been peer-reviewed.
The party problem was first stated in 1930 by the British mathematician and logician Frank Ramsey. One way to express it is to imagine a number R of people gathered together in a room, each of whom is either a friend or a stranger to the others. Say you are seeking a group of size k who are either all friends or all strangers. For a given k, what is the smallest R(k) that’s guaranteed to satisfy that condition? It has long been known that any group of 6 people contains at least 3 friends or 3 mutual strangers, and that any group of 18 contains at least 4 friends or 4 strangers. But already for the number 5, the exact solution R(5) is unknown, except that it has to be between 43 and 48.
The problem can be mapped onto the mathematical theory of networks, the abstract objects made of nodes and links connecting them. Each node will represent a person at the party, and any two people are connected by a link, which is colour-coded — red if two people know each other, and blue if they do not. The question then becomes, how large does a network need to be to guarantee that it contains at least one all-blue 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 4k. That bound is far from optimal: for example, for k = 4, it gives 44 = 256, whereas it is known that 18 would suffice. But the formula at least gives an upper bound that’s valid for any k.
The question that has tantalized combinatorialists since then is whether this upper bound can be any smaller — whether it can be shown that there is some bound Ck for which C is less than 4. Even to lower it by a tiny amount, says Sahasrabudhe, “would be an exponential improvement over what was known [previously]”, meaning that revising the bounds on C is the best possible way to improve on the earlier results.
The four researchers have now shown that the upper bound can be reduced at least to (3.9995)k. The result could have important ramifications for other areas of maths — in particular, for the study of networks that have an element of randomness, which can crop up in real-world problems ranging from epidemiology to optimization and scheduling problems, as well as for number theory and geometry.
Books and networks
The collaboration of the four researchers began in 2018, when Sahasrabudhe was visiting IMPA. Inspired by work on Ramsey’s theorem by combinatorialist David Conlon of the California Institute of Technology in Pasadena, the team was able rather quickly to sketch an outline of what a proof might look like. “This turned out to be just the beginning of a long road ahead,” says Sahasrabudhe.
Conlon’s work suggested an approach involving auxiliary networks known as ‘books’. The researchers set about devising an algorithm for constructing 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 they had found a way around the problem. “By early February, we had a good idea of how we could use these ideas to obtain the exponential improvement”, says Sahasrabudhe. “We were ready to go public in mid-March.”
Their proof has not yet been checked by others, he cautions. “Now that the paper is public, the community will enter a period of validating, simplifying, digesting and improving our work. It will be exciting to see where others will take the ideas.”
“The authors used elementary methods in an extremely clever way”, Gowers told Nature. He expects that the result will stand up. “They had a huge incentive to be careful, and, I am told, were indeed extremely careful. All four are amazing mathematicians who have done wonderful work in the past.” He adds that Sahasrabudhe’s presentation had “a very convincing story about what was going on”.
“The proof was very different from the kind of argument I had tried to find,” Gowers adds, “and I don’t think I would ever have found it.”
“This is a problem that has proven persistently difficult, despite being enormously well studied for almost a hundred years,” says Conlon. “Their progress is a stunning success.”
These hardy ants build their own landmarks in the desert
Daily briefing: We are exceeding the limits of Earth’s ability to support us
“It’s a vote for hope”: first gene therapy for muscular dystrophy nears approval, but will it work?