Erdős and the Probabilistic Method: Proving Things Exist by Chance
Paul Erdős had no home, no job in the ordinary sense, and almost no possessions. He spent his life traveling between universities with a suitcase, arriving on a colleague's doorstep with the line "my brain is open," and leaving behind a stream of theorems and unsolved problems that mathematicians are still working through today. Among everything he created, one idea stands out for changing how proofs are done at all. It is called the probabilistic method, and at its heart is a move that sounds almost like cheating: proving that something exists by refusing to build it.
The Question: When Is Order Unavoidable?
Start with a simple-sounding puzzle. At a party of six people, any two are either friends or strangers. It turns out that among any six people, you can always find three who are all mutual friends, or three who are all mutual strangers. Order forces itself to appear. The branch of mathematics that studies when this must happen is Ramsey theory, and it attaches a number to the question.
Ramsey's theorem guarantees these numbers exist, but it does not say how big they are. The natural follow-up is: how large can a group get while still avoiding any monochromatic cluster of size k? Answering that means proving such a clever coloring exists. And this is exactly where building one by hand becomes hopeless, because the number of possible colorings is astronomical.
Erdős's Move: Don't Build It, Count It
Erdős's insight, in 1947, was to stop trying to design a good coloring and instead color completely at random, then let arithmetic do the work. The argument is short enough to follow in full.
Color every connection by flipping a coin
Take n people and consider the complete network where every pair is joined by an edge. Color each edge independently at random, red or blue, each with probability one half. No cleverness, no design. Just a fair coin for every single edge.
Measure how likely one group is to be monochromatic
Fix any particular set of k people. Among them there are C(k,2) edges, that is k(k-1)/2 connections. For all of those edges to share a single color is unlikely: the probability is 2 × (1/2)^C(k,2), since there are two colors and every one of the C(k,2) coin flips has to agree. Call this small number p.
Add up the expected number of bad groups
There are C(n,k) different groups of k people to worry about. By the linearity of expectation, the expected number of fully monochromatic groups is just the count of groups times the probability for each one: C(n,k) × 2 × (1/2)^C(k,2). This single expression captures, on average, how many one-color clusters a random coloring will contain.
If the average is below 1, a flawless coloring must exist
Now choose n to be roughly 2^(k/2). With that choice, the expected number above works out to be less than 1. But a count of actual monochromatic groups is a whole number, and if the average over all colorings is below 1, then at least one coloring must score 0. That coloring has no monochromatic group of size k at all. Therefore R(k,k) is larger than n, which is about 2^(k/2).
Read that last step again, because it is the whole magic. We never produced a good coloring. We never described one. We showed that the average coloring is so close to flawless that a perfect one is forced to exist somewhere in the pile. The proof hands you certainty about a specific object while pointing at no object in particular.
Why This Was Revolutionary
Before Erdős, proving something existed almost always meant constructing it, or at least describing a procedure that would. The probabilistic method broke that expectation. It established that randomness itself could serve as a proof: if a random attempt succeeds with any probability above zero, success is possible, full stop.
This nonconstructive flavor puts the argument in the same family as some of the most elegant results in mathematics. Cantor's diagonal argument also proves the existence of something, a number missing from any list, through pure logical force rather than explicit construction. Both share that quiet, almost unsettling power: the conclusion is airtight even though it never shows you the thing it promises. The randomness here rests on the same foundations covered in understanding probability intuitively, where the idea of an expected value, the engine of step three, gets built up from scratch.
The Erdős Problems and Their AI Moment
Erdős did not only prove theorems. He posed problems, hundreds of them, often attaching small cash prizes that ranged from a few dollars for a tricky exercise to thousands for a question he believed was genuinely deep. Many of those problems are still open, and they have been carefully catalogued and maintained at erdosproblems.com.
The Zen of It
The probabilistic method is beautiful for the same reason a good magic trick is: you watch every step, you cannot find the place where you were fooled, and yet the result still feels impossible. There is no sleight of hand. The expected value really is below one, and a whole number below its own average really must dip to zero somewhere. The certainty is total, the construction is absent, and both of those things are true at once.
That is the lasting lesson Erdős left behind. Existence and construction are not the same thing. Sometimes the cleanest way to know a perfect object is out there is to prove that the average object is almost perfect, and let the gap do the rest. For another result where a single line ties together ideas that seem unrelated, Euler's identity offers the opposite kind of beauty: where Erdős conjures existence from counting, Euler pins down one exact and inevitable number.
Common Questions
- What is the probabilistic method?
- It is a way of proving that an object with some property exists, without constructing the object directly. You build a random version of the thing, show that the probability of it having the property you want is greater than zero, and conclude that at least one such object must exist. Paul Erdős pioneered the technique, and it is now a central tool in combinatorics and computer science.
- What did Erdős prove with it?
- His landmark 1947 result gave a lower bound on Ramsey numbers: he showed that the diagonal Ramsey number R(k,k) is larger than 2^(k/2). In plain terms, there exist ways to color the connections in a large network with two colors so that no large group is connected entirely in a single color. He proved these colorings exist without ever exhibiting one, just by counting.
- How can you prove something exists without building it?
- By using averages. If you pick an object at random and compute the expected number of flaws it has, and that expected number comes out below 1, then at least one object in the pool must have zero flaws. A random pick whose average flaw count is less than one guarantees a perfect example is sitting somewhere in the collection, even though the argument never points to which one it is.
- What is a Ramsey number?
- The Ramsey number R(k,k) is the smallest group size that forces order to appear no matter how you arrange things. Concretely, R(k,k) is the smallest number of people such that, however you split every pair into friends or strangers, you are guaranteed a group of k people who are all mutual friends or all mutual strangers. Ramsey's theorem says these numbers exist; Erdős's method shows they grow very fast.
- Why is the probabilistic method important today?
- It turned randomness into a proof technique, and that idea now runs through combinatorics, algorithm design, coding theory, and theoretical computer science. Many results about networks and algorithms are still proved by showing a random construction works with positive probability. The method is also why a large fraction of Erdős's own problems remain active research targets.
Enjoyed thinking this through?
Math Zen turns this kind of intuition into daily practice, with adaptive problems across 24 math topics.
