After 80 Years, Mathematicians Sharpen the Famed Erdős Method

There is a strange way to prove that something exists in mathematics: refuse to build it. Instead of constructing the object you want, you describe a giant collection of candidates, pick one purely at random, and show that the odds of landing on a winner are greater than zero. If the probability is not zero, then at least one winner must be sitting in the pile, even if you can never point to it. This sleight of hand is called the probabilistic method, and it has quietly reshaped large parts of mathematics and computer science. A result reported this week shows that the method, after eight decades, can still be made sharper.

The technique is bound up with the name of Paul Erdős, the prolific and itinerant Hungarian mathematician who turned randomness into a general-purpose tool. In 1947 he used it to settle a stubborn question about networks, and the trick has been multiplying ever since.

What the probabilistic method actually does

Start with a network, which mathematicians call a graph: a set of points, the vertices, joined by lines, the edges. The question Erdős cared about belongs to Ramsey theory, the study of how much order is unavoidable in a large enough structure. Imagine coloring every connection in a network with one of two colors. Ramsey theory says that once the network is big enough, you cannot avoid a sizable group of points all linked in a single color. The hard part is pinning down how big "big enough" has to be.

Erdős attacked the reverse direction. To show that fairly large networks can still dodge such a monochromatic group, he did not design a clever network by hand. He colored the edges at random, computed the expected number of unwanted groups, and showed that this expectation was small enough that some coloring had to avoid them entirely. No example was ever exhibited. The existence followed from the arithmetic of chance alone.

That move, now called a first-moment argument, became a template. Over the years mathematicians layered on refinements: deletion, in which you throw out the few bad cases that randomness leaves behind; second-moment methods, which control how far outcomes stray from the average; and the Lovász Local Lemma, which handles many rare failures that barely interact. Each addition let the method reach problems Erdős never touched, from testing whether a number is prime to designing reliable circuits.

Why the original problem stalled

Here is the irony at the center of this week's news. While the probabilistic method spread everywhere, the specific network question that launched it barely budged. For roughly eighty years, the best known bounds on those Ramsey numbers sat close to where Erdős and his contemporaries left them. Randomness gave a strong starting estimate, and then resisted improvement, as if the simple random coloring were already near the limit of what chance could reveal.

The new work, described in Quanta Magazine, breaks that stall by changing what gets randomized. Rather than coloring a fixed network blindly, the upgraded approach builds in extra structure before chance is applied, steering the random choice toward configurations more likely to succeed. The result is a measurable gain on a bound that had looked frozen, and a demonstration that Erdős's core idea still has room to grow when paired with the right scaffolding.

Why a bound on networks matters

It is reasonable to ask why a fractional improvement to an abstract estimate deserves attention. The answer is that the probabilistic method is one of the load-bearing tools of modern combinatorics, and progress on its founding problem tends to ripple outward. The same reasoning that bounds Ramsey numbers underlies how engineers analyze error-correcting codes, how computer scientists argue that fast randomized algorithms work, and how researchers reason about the structure of real networks. As we noted in our look at how many shuffles randomize a deck of cards, questions that sound like parlor games often carry the machinery used to tame randomness across science.

There is also a lesson about how mathematics moves. The probabilistic method is non-constructive by design: it promises that an object exists without telling you how to find it. That tension between knowing something is there and being able to produce it runs through much of the field, including the careful counting we described in our explainer on the elementary particles. The new upgrade does not resolve that tension. It widens the gap a little less, which in this part of mathematics counts as real progress.

Erdős liked to speak of an imaginary book in which the most elegant proof of every theorem was already written. The probabilistic method, with its refusal to do the obvious work of construction, has always felt like a page torn from it. Eight decades on, mathematicians are still finding that the page has more to say.