{"id":512368,"date":"2026-06-26T16:25:18","date_gmt":"2026-06-26T16:25:18","guid":{"rendered":"https:\/\/www.newsbeep.com\/il\/512368\/"},"modified":"2026-06-26T16:25:18","modified_gmt":"2026-06-26T16:25:18","slug":"after-80-years-mathematicians-give-famed-erdos-method-an-upgrade","status":"publish","type":"post","link":"https:\/\/www.newsbeep.com\/il\/512368\/","title":{"rendered":"After 80 Years, Mathematicians Give Famed \u2018Erd\u0151s Method\u2019 an Upgrade"},"content":{"rendered":"

In 1947, Paul Erd\u0151s, the itinerant Hungarian mathematician, introduced what would become one of math\u2019s most powerful tools. He wanted to prove that a certain kind of object existed \u2014 in this case, a network made of interconnected nodes. But strangely, his proof didn\u2019t specify how to build it. Instead, he showed that if you consider all networks and select one at random, the chances that you\u2019ll find a network with the property you want is greater than zero. That means that the desired network is out there somewhere, even if you know almost nothing about it.<\/p>\n

Erd\u0151s\u2019 approach, known as the probabilistic method, was simple but revolutionary. Before its development, \u201cif I\u2019m telling you that certain objects exist, you would tell me, \u2018Show me,\u2019\u201d said Benny Sudakov<\/a>, a mathematician at the Swiss Federal Institute of Technology Zurich. \u201cBut certain objects are so unusual that it\u2019s hard for us to grasp that they exist at all.\u201d<\/p>\n

Erd\u0151s\u2019 technique overcame this difficulty, demonstrating that randomness could be used in ways mathematicians had never imagined. \u201cIt was just astounding that you would use randomness,\u201d said Joel Spencer<\/a> of New York University. \u201cNow, that\u2019s the baseline.\u201d<\/p>\n

Today, the probabilistic method is used across mathematics and computer science \u2014 to figure out if a number is prime, to design better circuits, or to clean up data without introducing biases.<\/p>\n

Researchers have strengthened the technique in various ways. But the original focus of the probabilistic method \u2014 the question about networks that Erd\u0151s sought to answer \u2014 has seen very little progress. For eight decades, mathematicians were unable to significantly improve on the solution that Erd\u0151s came up with.<\/p>\n

That\u2019s now finally starting to change.<\/p>\n

A Voice in the Wilderness<\/p>\n

Imagine a network of nodes \u2014 a graph \u2014 in which every pair of nodes is connected by an edge.<\/p>\n

\"\"\"\" <\/p>\n

Mark Belan\/Quanta Magazine<\/p>\n

Now color each edge either red or blue, but with one caveat: Don\u2019t create any large clusters of nodes that are all connected by edges of the same color. These forbidden structures are called monochromatic cliques. Here\u2019s a monochromatic clique consisting of three nodes, which mathematicians call a clique of size 3:<\/p>\n

\"\"\"\" <\/p>\n

If your graph has enough nodes, it will be impossible to avoid creating a monochromatic clique, no matter how you color the edges. For instance, if you want to avoid a clique of size 3, your graph can have at most five nodes. A six-node graph will always have one:<\/p>\n

\"\"\"\" <\/p>\n

Mathematicians therefore say that the \u201cRamsey number\u201d for a clique of size 3, denoted R(3), is 6. Ramsey numbers measure how big graphs can get before the forbidden pattern inevitably emerges.<\/p>\n

You can also have Ramsey numbers for red and blue cliques of different sizes. For example, you can color an eight-node graph so that it has no red cliques of size 3 or blue cliques of size 4. But if you add one more node to your graph, you will be forced to create at least one red or blue clique. Therefore, the Ramsey number R(3, 4) is 9.<\/p>\n

\"\"\"\" <\/p>\n

As the cliques you want to avoid get bigger, the problem gets more and more difficult to solve. Mathematicians have been able to calculate only a handful of the smallest Ramsey numbers. \u201cIt\u2019s very hard to create something that has no structure,\u201d said Paul Horn<\/a> of the University of Denver. \u201cMaybe it\u2019s because we\u2019re human and we\u2019re subject to our biases.\u201d<\/p>\n

And so mathematicians have spent decades trying to find better and better approximations of Ramsey numbers. That\u2019s what Erd\u0151s was trying to do when he introduced his probabilistic method in 1947. Instead of building clique-free graphs directly, he considered every possible way to color a graph, then showed that at least some nonzero fraction of them must be clique-free.<\/p>\n

\"\"\"\" <\/p>\n

Erd\u0151s used this argument to prove that, if you forbid red and blue cliques of size k, the Ramsey number R(k) must be bigger than $latex \\sqrt{2}^k$. Ramsey numbers for same-size red and blue cliques are called diagonal Ramsey numbers. Erd\u0151s could similarly get a lower bound on \u201coff-diagonal\u201d Ramsey numbers R(k, l), in which you forbid red cliques of size k and blue cliques of size l.<\/p>\n

The proof was just a few lines long. But it was completely unexpected.<\/p>\n

At first, mathematicians were loath to follow his lead. They wanted concrete examples. \u201cFor many years, Erd\u0151s was like a voice in the wilderness,\u201d Spencer said. \u201cHe was getting these amazing results using randomness, and people had never done that before.\u201d<\/p>\n

But soon the probabilistic method proved its worth. It\u2019s now one of the most ubiquitous techniques in \u201cdiscrete\u201d math, the study of objects (like graphs) that are separate rather than continuous. And it has seeped out of math into physics and computer science<\/a>. \u201cThe randomness, I think, just helps us get at something that is otherwise very ethereal,\u201d Horn said.<\/p>\n

More recently, mathematicians have been able to adapt Erd\u0151s\u2019 method to get better estimates of Ramsey numbers where the forbidden cliques differ vastly in size<\/a>. For instance, in 2025 Horn and three colleagues used an updated version of Erd\u0151s\u2019 method to prove a more precise lower bound for R(3, l)<\/a>, where l grows arbitrarily large. (That work, in turn, led to a major breakthrough<\/a> in graph theory.)<\/p>\n

\"\" <\/p>\n

Paul Erd\u0151s figured out how to use randomness to prove that certain mathematical objects exist, even if you don\u2019t know how to construct them. His technique, today known as the probabilistic method, transformed many branches of math and computer science.<\/p>\n

Archives of the Mathematisches Forschungsinstitut Oberwolfach \u00a9Gabriella Bollobas<\/p>\n

But when it came to Ramsey numbers where the forbidden cliques weren\u2019t so different in size \u2014 particularly diagonal Ramsey numbers, the object of Erd\u0151s\u2019 original interest \u2014 the probabilistic method stalled. Say you forbid cliques of size 1,000. Erd\u0151s showed that R(1,000) must be bigger than about 2500. Eight decades of effort changed that bound to about 2501. Similarly, from the 1970s onward, progress remained stock-still for off-diagonal Ramsey numbers where the forbidden red and blue cliques are both relatively large.<\/p>\n

Then along came a graduate student with barely any expertise in Ramsey theory.<\/p>\n

Correlated Coloring<\/p>\n

Wujie Shen had spent his first few semesters at Tsinghua University focused mainly on geometry and topology. But in the spring of 2024, he came across a paper on Ramsey numbers<\/a> that captivated him.<\/p>\n

He knew how Erd\u0151s\u2019 method worked: You flip a coin to determine the color of each edge of your graph: Heads, the edge is red; tails, it\u2019s blue. You then calculate the probability that you\u2019ll get a clique-free coloring. But this calculation gets very difficult for larger graphs. Shen wondered whether there was a random model that could produce clique-free colorings more efficiently than Erd\u0151s\u2019 approach.<\/p>\n

\"\"\"\" <\/p>\n

Given Shen\u2019s training, it\u2019s perhaps no surprise that the model he came up with involved geometry. Typically, graph colorings don\u2019t invoke geometry: All that matters to mathematicians is which nodes are connected by a red edge, and which are connected by a blue one. Whether those nodes sit close together or are scattered throughout space has no significance.<\/p>\n

But Shen wanted to use geometry to help him decide which edges to color red and which to color blue. In particular, he wanted to use the geometry of high-dimensional spheres \u2014 that is, sets of points that are equidistant from a single central point.<\/p>\n

These spheres \u201cmess with all our intuitions completely,\u201d said David Conlon<\/a> of the California Institute of Technology. Many of our assumptions about what a sphere looks like are no longer true in high dimensions: A high-dimensional sphere has a tiny volume and massive surface area, and most of its points lie on the equator. It\u2019s \u201cpretty complicated to work with,\u201d Sudakov said.<\/p>\n

But Shen and two colleagues \u2014 Jie Ma<\/a>, who was visiting Tsinghua to teach for the fall term, and Ma\u2019s graduate student Shengjie Xie \u2014 wanted to try. Their method: First, place nodes one by one onto the surface of a high-dimensional sphere. Choose each node\u2019s position at random \u2014 any point on the sphere is fair game, and the placement of each node has no influence over the placement of any other node.<\/p>\n

Once you\u2019ve placed all the nodes, color each edge based on the distance between the nodes. If two points are more than some fixed distance apart (which will happen with a probability of less than 1\/2), color the edge connecting them red. If they\u2019re closer together, color the edge blue.<\/p>\n

\"\"\"\" <\/p>\n

From left\/top: Jie Ma, Wujie Shen, and Shengjie Xie used the strange geometry of high-dimensional spheres to make progress on a problem that had been stalled for decades.<\/p>\n

From left\/top: Courtesy of Jie Ma; Courtesy of Wujie Shen; Ziyuan Zhao<\/p>\n

With this approach, the graphs that Ma, Shen, and Xie created were less likely to form a red clique. That\u2019s because to form a large red clique, you need many nodes that are all far away from one another. With only so much space on the sphere, this is unlikely to happen.<\/p>\n

But there\u2019s a catch. By the same token, this method also produces a greater fraction of colorings that have blue cliques than Erd\u0151s\u2019 does. \u201cThere\u2019s a trade-off that looks like it really helps in one color, but it doesn\u2019t help at all in the other color,\u201d Conlon said. \u201cWhy bother?\u201d<\/p>\n

Even so, Ma, Shen, and Xie were hopeful. They tested their method on smaller graphs, and it seemed to work: Among the tens of thousands of bad colorings it generated, there was still a nonzero chance of getting a good clique-free coloring as well. That reassured them that the benefits could outweigh the costs, even for much bigger graphs.<\/p>\n

They then set out to prove it. The key turned out to be the very weird geometry of high-dimensional spheres.<\/p>\n

Ultimately, to show that they could avoid cliques of a particular size, Ma, Shen, and Xie needed to limit the probability that their randomly placed nodes formed clusters that were all far apart, or all close together. They realized that if they drew lines from each node to the sphere\u2019s center, those lines would almost all be perpendicular or close to perpendicular. That doesn\u2019t happen if you randomly place nodes on a familiar two-dimensional sphere: Most nodes will not lie on perpendicular lines. But the team was able to prove that it was true in the much higher dimensions that they were working in.<\/p>\n

That, in turn, restricted how far nodes could be from one another \u2014 thereby limiting their chances of forming a monochromatic clique.<\/p>\n

After a year and 40 pages of dense computations, the trio posted their paper<\/a> in July 2025. They\u2019d improved Erd\u0151s\u2019 lower bound on Ramsey numbers \u2014 but only when the forbidden blue cliques are larger than the red ones. When the blue cliques are just as small as the red ones, the benefits of the new approach disappear.<\/p>\n

\"\"\"\" <\/p>\n

Still, when you want to avoid red cliques that are, say, half as large as blue ones, Ma, Shen, and Xie managed to nudge Erd\u0151s\u2019 growth rate of $latex ((\\sqrt{5} + 1)\/2)^k$ up to $latex ((\\sqrt{5} + 1)\/2 + 10^{-21})^k$. While the change is tiny, their proof marks the first improvement for near-diagonal Ramsey numbers in 50 years.<\/p>\n

\u201cIt\u2019s lucky, and we feel like all our efforts are rewarded,\u201d Ma said. \u201cBut it was tough for a long time.\u201d<\/p>\n

\u201cIt\u2019s a bit shocking that a familiar thing works for a familiar problem,\u201d said Julian Sahasrabudhe<\/a> of the University of Cambridge. Their technique, he said, \u201cwas hidden in plain view.\u201d<\/p>\n

The Probabilistic Playground<\/p>\n

Ma, Shen, and Xie\u2019s proof has already generated a spate of further progress. In December 2025, Sudakov and two of his graduate students drastically simplified the team\u2019s coloring model<\/a>, improving their new bounds even further. Others have since used the model to estimate Ramsey numbers<\/a> that involve three colors, not two.<\/p>\n

That\u2019s in keeping with the probabilistic method\u2019s long history. For the past 80 years, mathematicians have been tinkering with Erd\u0151s\u2019 randomness-based technique, finding more and more ways to mix in additional structure to boost its power. Inevitably, these new techniques have then proved useful elsewhere. \u201cIt\u2019s a very fruitful playground for ideas,\u201d Sudakov said.<\/p>\n

Ma, Shen, and Xie\u2019s work, then, is the latest chapter in this decades-old story. But it\u2019s also the first one in a long time to revisit the near-diagonal Ramsey numbers.<\/p>\n

The team\u2019s new contribution \u2014 a geometric approach \u2014 might lead to more progress on that stubborn problem. Although the probabilistic method hasn\u2019t been perfected yet, \u201cit\u2019s really very powerful now,\u201d Spencer said. \u201cIt\u2019s really changed so much.\u201d<\/p>\n

\"\"\"\" <\/p>\n","protected":false},"excerpt":{"rendered":"In 1947, Paul Erd\u0151s, the itinerant Hungarian mathematician, introduced what would become one of math\u2019s most powerful tools.…\n","protected":false},"author":2,"featured_media":512369,"comment_status":"","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[85,46,125],"class_list":["post-512368","post","type-post","status-publish","format-standard","has-post-thumbnail","category-technology","tag-il","tag-israel","tag-technology"],"_links":{"self":[{"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/posts\/512368","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/comments?post=512368"}],"version-history":[{"count":0,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/posts\/512368\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/media\/512369"}],"wp:attachment":[{"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/media?parent=512368"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/categories?post=512368"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.newsbeep.com\/il\/wp-json\/wp\/v2\/tags?post=512368"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}