After 80 Years, Mathematicians Give Famed ‘Erdős Method’ an Upgrade | Quanta Magazine
About Quanta
Search
Search for:
Search<br>Search
Newsletter
Get the latest news delivered to your inbox.
Subscribe
Recent newsletters
Follow Quanta
Youtube
RSS
An editorially independent publication supported by the Simons Foundation.
Type search term(s) and press enter
What are you looking for?
Search
Home
After 80 Years, Mathematicians Give Famed ‘Erdős Method’ an Upgrade
Comment
Save Article
Read Later
Share
Copied!
Copy link
Ycombinator
Comment
Comments
Save Article<br>Read Later
Read Later
graph theory
After 80 Years, Mathematicians Give Famed ‘Erdős Method’ an Upgrade
By
Leila Sloman
June 26, 2026
Decades ago, Paul Erdős used randomness to illuminate the vast and weird world of networks. Now mathematicians are making his technique even more powerful.
Comment
Save Article
Read Later
Robert Neubecker for Quanta Magazine
By Leila Sloman
Contributing Correspondent
June 26, 2026
View PDF/Print Mode
combinatorics
Erdős conjecture
graph theory
mathematics
Ramsey theory
All topics
In 1947, Paul Erdős, the itinerant Hungarian mathematician, introduced what would become one of math’s most powerful tools. He wanted to prove that a certain kind of object existed — in this case, a network made of interconnected nodes. But strangely, his proof didn’t specify how to build it. Instead, he showed that if you consider all networks and select one at random, the chances that you’ll 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.
Erdős’ approach, known as the probabilistic method, was simple but revolutionary. Before its development, “if I’m telling you that certain objects exist, you would tell me, ‘Show me,’” said Benny Sudakov, a mathematician at the Swiss Federal Institute of Technology Zurich. “But certain objects are so unusual that it’s hard for us to grasp that they exist at all.”
Erdős’ technique overcame this difficulty, demonstrating that randomness could be used in ways mathematicians had never imagined. “It was just astounding that you would use randomness,” said Joel Spencer of New York University. “Now, that’s the baseline.”
Today, the probabilistic method is used across mathematics and computer science — to figure out if a number is prime, to design better circuits, or to clean up data without introducing biases.
Researchers have strengthened the technique in various ways. But the original focus of the probabilistic method — the question about networks that Erdős sought to answer — has seen very little progress. For eight decades, mathematicians were unable to significantly improve on the solution that Erdős came up with.
That’s now finally starting to change.
A Voice in the Wilderness
Imagine a network of nodes — a graph — in which every pair of nodes is connected by an edge.
Mark Belan/Quanta Magazine
Now color each edge either red or blue, but with one caveat: Don’t create any large clusters of nodes that are all connected by edges of the same color. These forbidden structures are called monochromatic cliques. Here’s a monochromatic clique consisting of three nodes, which mathematicians call a clique of size 3:
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:
Mathematicians therefore say that the “Ramsey number” 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.
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.
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. “It’s very hard to create something that has no structure,” said Paul Horn of the University of Denver. “Maybe it’s because we’re human and we’re subject to our biases.”
And so mathematicians have spent decades trying to find better and better approximations of Ramsey numbers. That’s what Erdős 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.
Erdős used this argument to prove that, if you forbid red and blue cliques...