For most of the past century, mathematicians have been exploring the limits of Ramsey theory, the study of order hiding inside chaos—or, more accurately, how much disorder can be packed into a system before order must inevitably emerge. Progress has been frustratingly slow, but now a potential breakthrough result is pointing the way toward more rapid advances—and a clearer view of the still-hazy transition between randomness and structure.
The systems in question are called graphs: mathematical networks made of points connected by lines. These graphs can represent anything interconnected—from friendships to airline routes to molecules. And as any graph grows, sooner or later it will include either a tight-knit group in which everything is connected to everything else—a “clique”—or encompass a large collection of points with no connections between them at all, known as an “independent set.”
In a new proof posted to the preprint server arXiv.org last month, Domagoj Bradač of the Swiss Federal Institute of Technology in Lausanne has dramatically tightened key constraints on where this transition can take place, toppling a barrier that has bewildered researchers for decades. A few weeks later, an OpenAI reasoning model unexpectedly improved his result, essentially eliminating what little uncertainty remained on Bradač’s constraints to effectively conclude what had been a 90-year search.
On supporting science journalism
If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Bradač’s work looked at Ramsey numbers, which tell mathematicians exactly how large a graph can become before it’s guaranteed to gain a clique or independent set. In a social network, for example, the Ramsey number R(3,10) describes how many people the network can have before it’s certain to contain either three mutual friends or 10 people who are all strangers to one another.
These numbers are notoriously difficult to calculate. Mathematicians have determined fewer than 30 Ramsey numbers exactly, and even seemingly modest cases remain unsolved—no one, for instance, knows the value of R(3,10). Instead researchers usually settle for boxing Ramsey numbers in by proving they must lie somewhere between an upper and a lower bound.
Bradač’s proof concerns off-diagonal Ramsey numbers, which allow for large differences between the size of a clique and the size of an independent set. Returning to our social network example, R(3,10) could be considered off-diagonal, given that 3 and 10 are reasonably far apart. But mathematicians imagine keeping the “three mutual friends” part fixed while asking about larger and larger groups of strangers. Instead of R(3,10), you might ask about R(3,100), then R(3,1,000), and so on. Rather than chasing one elusive number at a time, mathematicians study how these Ramsey numbers grow as the graphs become larger—and how to hem them in.
You can think of these bounds as a mathematical version of the trash compactor from Star Wars. One wall is the lower bound, and the other is the upper bound. Every new theorem ratchets one wall inward, squeezing the gap a little tighter. If the walls ever meet, we’ll find the secret to the growth of these numbers smushed between them. Bradač’s proof—and its subsequent refinement—brings the walls deliciously close to touching. (Sorry, Chewie.)
When searching for these bounds, the primary tool has long been the probabilistic method—the once-controversial idea that you can prove something exists without ever actually finding it. Originally developed in the 1940s by Paul Erdős in part to study Ramsey theory, the method shows that if a randomly assembled graph has a nonzero chance of possessing the desired properties, then at least one such graph must exist—even if no one can actually point to it.
“In an ideal world I would just tell you, look, here’s a graph, and you would be done,” Bradač says. “Unfortunately, we don’t know how to do this.”
Instead—and perhaps thematically—Bradač begins with a little more structure before introducing the necessary randomness. He first stitches together a much larger graph than he ultimately needs—one carefully chosen for its geometric and algebraic structure.
“Geometry is something that we understand much better than graph theory in some ways,” says Marcelo Campos, an assistant professor at Brazil’s National Institute for Pure and Applied Mathematics, who was not involved with the work. “If I draw a graph coming from geometry, I know that it will have some properties inherited from just the geometry. So it’s much easier to prove some fact that comes from this than to try to cook up the graph explicitly.”
Once that structure is in place, in comes the chaos. Bradač “zooms in” on the larger graph, randomly selecting a subgraph of the size he needs. By strategically removing a relatively small number of troublesome vertices, he can restore the graph’s carefully balanced properties without sacrificing most of its size.
The result is a family of graphs that can grow far larger than previously thought while still avoiding both forbidden patterns: small cliques and large independent sets. In practical terms, Bradač’s work shows that these “pattern-free” graphs can survive much longer than mathematicians have ever been able to otherwise prove. More importantly, his estimate comes astonishingly close to the best upper bound known—a ceiling that has stood, largely unchanged, since the 1930s.
“This is a tremendous breakthrough,” says Joel Spencer, an emeritus professor at New York University, who frequently collaborated with Erdős.
According to Spencer, groundbreaking results like this rarely remain unaltered for long. Once a major proof appears, mathematicians immediately begin probing it, looking for ways to sharpen the argument or squeeze out slightly stronger bounds.
What made this case unusual was that the earliest refinements came not from another mathematician, but from an AI reasoning model.
Shortly after posting the preprint, Bradač was contacted by researchers at OpenAI. They had tested the proof with one of the company’s internal reasoning models, which found a refinement that tightened the bound even further. Together, the two results now match the best-known upper bound up to polylogarithmic factors—a tiny remaining gap that many mathematicians regard as the last significant obstacle to understanding the true growth of these Ramsey numbers.
Mehtaab Sawhney, a mathematician working on OpenAI’s math research team, says that the timing is a coincidence—they happened to ask their model about off-diagonal Ramsey numbers just after the preprint was available for the LLM to digest. “We do not systematically attempt to improve newly posted arXiv papers,” he says. “In this case, a recent preprint happened to be relevant to the tested problem.”
Campos stresses that OpenAI’s refinement, while important, should not overshadow the conceptual leap made in the original work. “It turned out to be a very important tweak,” he says, “but it was very much based on the idea that was already there.”