In 1947, Paul Erdős, the itinerant Hungarian mathematician, launched what would turn into one in all math’s strongest instruments. He needed to show {that a} sure sort of object existed — on this case, a community product of interconnected nodes. However surprisingly, his proof didn’t specify tips on how to construct it. As a substitute, he confirmed that in case you contemplate all networks and choose one at random, the possibilities that you simply’ll discover a community with the property you need is bigger than zero. That implies that the specified community is on the market someplace, even when virtually nothing about it.
Erdős’ method, often known as the probabilistic methodology, was easy however revolutionary. Earlier than its improvement, “if I’m telling you that sure objects exist, you’d inform me, ‘Present me,’” stated Benny Sudakov, a mathematician on the Swiss Federal Institute of Expertise Zurich. “However sure objects are so uncommon that it’s laborious for us to understand that they exist in any respect.”
Erdős’ method overcame this issue, demonstrating that randomness may very well be utilized in methods mathematicians had by no means imagined. “It was simply astounding that you’d use randomness,” stated Joel Spencer of New York College. “Now, that’s the baseline.”
In the present day, the probabilistic methodology is used throughout arithmetic and laptop science — to determine if a quantity is prime, to design higher circuits, or to wash up information with out introducing biases.
Researchers have strengthened the method in varied methods. However the authentic focus of the probabilistic methodology — the query about networks that Erdős sought to reply — has seen little or no progress. For eight many years, mathematicians have been unable to considerably enhance on the answer that Erdős got here up with.
That’s now lastly beginning to change.
A Voice within the Wilderness
Think about a community of nodes — a graph — during which each pair of nodes is related by an edge.
Mark Belan/Quanta Journal
Now colour every edge both crimson or blue, however with one caveat: Don’t create any massive clusters of nodes which are all related by edges of the identical colour. These forbidden constructions are referred to as monochromatic cliques. Right here’s a monochromatic clique consisting of three nodes, which mathematicians name a clique of dimension 3:
In case your graph has sufficient nodes, it is going to be unattainable to keep away from making a monochromatic clique, irrespective of the way you colour the sides. As an illustration, if you wish to keep away from a clique of dimension 3, your graph can have at most 5 nodes. A six-node graph will all the time have one:
Mathematicians subsequently say that the “Ramsey quantity” for a clique of dimension 3, denoted R(3), is 6. Ramsey numbers measure how huge graphs can get earlier than the forbidden sample inevitably emerges.
You too can have Ramsey numbers for crimson and blue cliques of various sizes. For instance, you possibly can colour an eight-node graph in order that it has no crimson cliques of dimension 3 or blue cliques of dimension 4. However in case you add yet one more node to your graph, you may be pressured to create a minimum of one crimson or blue clique. Due to this fact, the Ramsey quantity R(3, 4) is 9.
Because the cliques you wish to keep away from get larger, the issue will get increasingly tough to resolve. Mathematicians have been capable of calculate solely a handful of the smallest Ramsey numbers. “It’s very laborious to create one thing that has no construction,” stated Paul Horn of the College of Denver. “Possibly it’s as a result of we’re human and we’re topic to our biases.”
And so mathematicians have spent many years looking for higher and higher approximations of Ramsey numbers. That’s what Erdős was attempting to do when he launched his probabilistic methodology in 1947. As a substitute of constructing clique-free graphs straight, he thought of each potential method to colour a graph, then confirmed that a minimum of some nonzero fraction of them have to be clique-free.
Erdős used this argument to show that, in case you forbid crimson and blue cliques of dimension ok, the Ramsey quantity R(ok) have to be larger than $latex sqrt{2}^ok$. Ramsey numbers for same-size crimson and blue cliques are referred to as diagonal Ramsey numbers. Erdős may equally get a decrease sure on “off-diagonal” Ramsey numbers R(ok, l), during which you forbid crimson cliques of dimension ok and blue cliques of dimension l.
The proof was only a few strains lengthy. Nevertheless it was utterly sudden.
At first, mathematicians have been loath to observe his lead. They needed concrete examples. “For a few years, Erdős was like a voice within the wilderness,” Spencer stated. “He was getting these superb outcomes utilizing randomness, and other people had by no means performed that earlier than.”
However quickly the probabilistic methodology proved its value. It’s now probably the most ubiquitous methods in “discrete” math, the research of objects (like graphs) which are separate somewhat than steady. And it has seeped out of math into physics and laptop science. “The randomness, I feel, simply helps us get at one thing that’s in any other case very ethereal,” Horn stated.
Extra not too long ago, mathematicians have been capable of adapt Erdős’ methodology to get higher estimates of Ramsey numbers the place the forbidden cliques differ vastly in dimension. As an illustration, in 2025 Horn and three colleagues used an up to date model of Erdős’ methodology to show a extra exact decrease sure for R(3, l), the place l grows arbitrarily massive. (That work, in flip, led to a significant breakthrough in graph principle.)
Paul Erdős discovered tips on how to use randomness to show that sure mathematical objects exist, even in case you don’t know tips on how to assemble them. His method, immediately often known as the probabilistic methodology, reworked many branches of math and laptop science.
Archives of the Mathematisches Forschungsinstitut Oberwolfach ©Gabriella Bollobas
However when it got here to Ramsey numbers the place the forbidden cliques weren’t so totally different in dimension — significantly diagonal Ramsey numbers, the item of Erdős’ authentic curiosity — the probabilistic methodology stalled. Say you forbid cliques of dimension 1,000. Erdős confirmed that R(1,000) have to be larger than about 2500. Eight many years of effort modified that sure to about 2501. Equally, from the Seventies onward, progress remained stock-still for off-diagonal Ramsey numbers the place the forbidden crimson and blue cliques are each comparatively massive.
Then alongside got here a graduate pupil with barely any experience in Ramsey principle.
Correlated Coloring
Wujie Shen had spent his first few semesters at Tsinghua College targeted primarily on geometry and topology. However within the spring of 2024, he got here throughout a paper on Ramsey numbers that captivated him.
He knew how Erdős’ methodology labored: You flip a coin to find out the colour of every fringe of your graph: Heads, the sting is crimson; tails, it’s blue. You then calculate the likelihood that you simply’ll get a clique-free coloring. However this calculation will get very tough for bigger graphs. Shen questioned whether or not there was a random mannequin that would produce clique-free colorings extra effectively than Erdős’ method.
Given Shen’s coaching, it’s maybe no shock that the mannequin he got here up with concerned geometry. Usually, graph colorings don’t invoke geometry: All that issues to mathematicians is which nodes are related by a crimson edge, and that are related by a blue one. Whether or not these nodes sit shut collectively or are scattered all through house has no significance.
However Shen needed to make use of geometry to assist him resolve which edges to paint crimson and which to paint blue. Specifically, he needed to make use of the geometry of high-dimensional spheres — that’s, units of factors which are equidistant from a single central level.
These spheres “mess with all our intuitions utterly,” stated David Conlon of the California Institute of Expertise. A lot of our assumptions about what a sphere appears to be like like are now not true in excessive dimensions: A high-dimensional sphere has a tiny quantity and large floor space, and most of its factors lie on the equator. It’s “fairly sophisticated to work with,” Sudakov stated.
However Shen and two colleagues — Jie Ma, who was visiting Tsinghua to show for the autumn time period, and Ma’s graduate pupil Shengjie Xie — needed to attempt. Their methodology: First, place nodes one after the other onto the floor of a high-dimensional sphere. Select every node’s place at random — any level on the sphere is honest recreation, and the location of every node has no affect over the location of another node.
When you’ve positioned all of the nodes, colour every edge primarily based on the gap between the nodes. If two factors are greater than some mounted distance aside (which can occur with a likelihood of lower than 1/2), colour the sting connecting them crimson. In the event that they’re nearer collectively, colour the sting blue.
From left/prime: Jie Ma, Wujie Shen, and Shengjie Xie used the unusual geometry of high-dimensional spheres to make progress on an issue that had been stalled for many years.
From left/prime: Courtesy of Jie Ma; Courtesy of Wujie Shen; Ziyuan Zhao
With this method, the graphs that Ma, Shen, and Xie created have been much less more likely to type a crimson clique. That’s as a result of to type a big crimson clique, you want many nodes which are all distant from each other. With solely a lot house on the sphere, that is unlikely to occur.
However there’s a catch. By the identical token, this methodology additionally produces a better fraction of colorings which have blue cliques than Erdős’ does. “There’s a trade-off that appears prefer it actually helps in a single colour, however it doesn’t assist in any respect within the different colour,” Conlon stated. “Why trouble?”
Even so, Ma, Shen, and Xie have been hopeful. They examined their methodology on smaller graphs, and it appeared to work: Among the many tens of 1000’s of unhealthy colorings it generated, there was nonetheless a nonzero probability of getting a great clique-free coloring as properly. That reassured them that the advantages may outweigh the prices, even for a lot larger graphs.
They then got down to show it. The important thing turned out to be the very bizarre geometry of high-dimensional spheres.
Finally, to indicate that they might keep away from cliques of a specific dimension, Ma, Shen, and Xie wanted to restrict the likelihood that their randomly positioned nodes shaped clusters that have been all far aside, or all shut collectively. They realized that in the event that they drew strains from every node to the sphere’s heart, these strains would virtually all be perpendicular or near perpendicular. That doesn’t occur in case you randomly place nodes on a well-recognized two-dimensional sphere: Most nodes won’t lie on perpendicular strains. However the crew was capable of show that it was true within the a lot greater dimensions that they have been working in.
That, in flip, restricted how far nodes may very well be from each other — thereby limiting their probabilities of forming a monochromatic clique.
After a 12 months and 40 pages of dense computations, the trio posted their paper in July 2025. They’d improved Erdős’ decrease sure on Ramsey numbers — however solely when the forbidden blue cliques are bigger than the crimson ones. When the blue cliques are simply as small because the crimson ones, the advantages of the brand new method disappear.
Nonetheless, while you wish to keep away from crimson cliques which are, say, half as massive as blue ones, Ma, Shen, and Xie managed to nudge Erdős’ development fee of $latex ((sqrt{5} + 1)/2)^ok$ as much as $latex ((sqrt{5} + 1)/2 + 10^{-21})^ok$. Whereas the change is tiny, their proof marks the primary enchancment for near-diagonal Ramsey numbers in 50 years.
“It’s fortunate, and we really feel like all our efforts are rewarded,” Ma stated. “Nevertheless it was powerful for a very long time.”
“It’s a bit stunning {that a} acquainted factor works for a well-recognized downside,” stated Julian Sahasrabudhe of the College of Cambridge. Their method, he stated, “was hidden in plain view.”
The Probabilistic Playground
Ma, Shen, and Xie’s proof has already generated a spate of additional progress. In December 2025, Sudakov and two of his graduate college students drastically simplified the crew’s coloring mannequin, bettering their new bounds even additional. Others have since used the mannequin to estimate Ramsey numbers that contain three colours, not two.
That’s in line with the probabilistic methodology’s lengthy historical past. For the previous 80 years, mathematicians have been tinkering with Erdős’ randomness-based method, discovering increasingly methods to combine in extra construction to spice up its energy. Inevitably, these new methods have then proved helpful elsewhere. “It’s a really fruitful playground for concepts,” Sudakov stated.
Ma, Shen, and Xie’s work, then, is the newest chapter on this decades-old story. Nevertheless it’s additionally the primary one in a very long time to revisit the near-diagonal Ramsey numbers.
The crew’s new contribution — a geometrical method — may result in extra progress on that cussed downside. Though the probabilistic methodology hasn’t been perfected but, “it’s actually very highly effective now,” Spencer stated. “It’s actually modified a lot.”
