Erdős proved colourings exist without ever building one, and invented a whole technique doing it
By the 1940s the upper bound on R(k,k) had been known for a decade: Erdős and Szekeres had shown it was less than 4ᵏ. The lower bound was in a different state entirely. To prove R(k,k) is large you must exhibit a colouring of a large complete graph with no monochromatic k-clique, and building such a colouring by hand gets hopeless almost immediately. The best anyone had was quadratic.
In 1947 Paul Erdős published a paper of under two pages containing an argument that takes about half of one. He did not build a colouring. He flipped a coin for every edge and computed the average number of monochromatic k-cliques. If that average comes out below 1, then at least one colouring must have zero — because you cannot have every outcome above the mean. The bound that fell out, R(k,k) > 2^(k/2), was exponentially better than anything constructed before it, and in its exponential shape it has never been improved.
The technique mattered more than the theorem. Proving that an object exists by showing a random object has a positive chance of being one is now called the probabilistic method, and it runs through combinatorics, theoretical computer science, coding theory and discrete geometry. It began here, as a remark about parties.
Here is the experiment Erdős never had to run. Colour every edge of the complete graph by an independent coin flip, then go looking for k vertices that are mutually joined in a single colour. Nothing about this colouring is designed — and yet for a surprisingly wide range of sizes, it works nearly every time.
Clean. The largest single-colour clique in this sample has 4 vertices, short of 5.
Coin flips are seeded, so this sample is reproducible: seed 20250601.
Every edge is coloured by an independent coin flip — nothing is being designed. Push n up and the clean fraction does not taper off, it falls off a shelf. The shelf begins near n = 11, the last size at which the expected number of monochromatic 5-cliques is still below 1, and by roughly twice that value not one sample in 200 survives.
Try it: It opens at eleven vertices and k = 5, the last size the first moment can vouch for — press New sample a few times and roughly three in five come out clean. Then press Sweep n. The clean fraction holds above 90% out to eight vertices, is still around 60% at n = 11 where the expected count crosses 1, and by about eighteen vertices not one sample in two hundred survives. The collapse is sharp, and it lands where the arithmetic says it should — the proof is not describing a rare accident, it is describing the typical case.
The argument has three moves and no cleverness at all. Count the ways the colouring could fail. Work out how likely each individual failure is. Add them up. If the total comes in under 1 then the failures cannot possibly cover every outcome, so some outcome dodges all of them at once — and that outcome is a colouring with no monochromatic clique.
126 sets of 4 vertices. Each one is a separate way for the colouring to fail, and no colouring has been looked at yet.
A fixed set of 4 vertices spans 6 edges. All 6 come up rose with probability 2⁻⁶, all sky with the same, so the set is monochromatic with probability 2⁻⁵ = 1 / 32.
That number does not depend on n at all. Growing the graph does not make any individual clique more likely — it only creates more of them.
126 × 1/32 = 3.938
At or above 1. The union bound is silent: it does not say a good colouring of K9 is impossible, only that this argument cannot produce one.
The chance of some clique going monochromatic is at most the sum of the individual chances. When that sum is under 1, the chance of none is strictly positive — and anything with positive probability happens somewhere.
Try it: At k = 4 and n = 6 there are fifteen candidate cliques, each monochromatic with probability 1/32, for a total of 0.469 — under 1, so a good colouring of six vertices exists. Push n to 7 and the total passes 1 and the argument goes quiet. It does not say a good colouring is impossible; R(4,4) is 18, so good colourings run all the way to seventeen vertices. It says only that this argument has stopped working.
The expected number of monochromatic k-cliques is C(n,k)·2^(1−C(k,2)), and the whole proof is the point where that quantity passes 1. Neither factor can be computed directly — C(60,30) already exceeds 10¹⁷ and 2^C(k,2) is 2¹⁹⁰ by k = 20 — so the curve below is built entirely from logarithms and only converted to a decimal where it is small enough to print.
The curve is the expected number of monochromatic 8-cliques in a random two-colouring of Kn, drawn across ∞ orders of magnitude. Anywhere in the green region the average is below 1, so a colouring with none must exist and R(8,8) is greater than 42. The blue mark is the bound Erdős actually published — 2^(k/2) is a deliberately loose simplification of the exact crossing, chosen because it is a formula rather than a search. One page of probability gives 42; every technique invented since has pushed the best known lower bound for R(8,8) only as far as 282.
Try it: Watch the two dashed lines separate as k grows. At k = 10 the exact crossing is at n = 100 while the published 2^(k/2) is only 32; at k = 20 it is 5,817 against 1,024. Erdős deliberately gave away that factor, because a clean formula travels further than a threshold you have to search for — and the shape of the bound, an exponential in k/2, is identical either way.
And now the embarrassment. Almost every colouring of a graph on 2^(k/2) vertices has no monochromatic k-clique — they are not rare, they are the overwhelming majority. Ask for one, explicitly, and mathematics has no answer. Nearly eighty years of work on explicit constructions has produced beautiful objects, and none of them reaches what a coin flip reaches in a single line.
| Year | Construction | Clique size it avoids | Explicit? |
|---|---|---|---|
| 1947 | A coin flip (Erdős) Proves a colouring exists. Produces nothing you could write down or check. | K ≈ 2 log₂ N N = 2^(K/2) | no |
| 1955 | Quadratic residues (Paley graphs) Join x and y when x − y is a square mod p. Fully explicit, checkable by hand, and at K = 4 it is exactly optimal — the Paley graph on 17 vertices is why R(4,4) is 18. | K ≈ √N N ≈ K² | yes |
| 1981 | Frankl and Wilson The first explicit family to beat every polynomial. Built from intersection theorems on set systems, not from graphs at all. | K = exp(O(√(log N · log log N))) quasi-polynomial in K | yes |
| 2012 | Barak, Rao, Shaltiel and Wigderson Randomness extractors enter the story: a graph that is hard to find becomes a function that is hard to predict. | K = N^o(1) sub-polynomial | yes |
| 2016 | Chattopadhyay and Zuckerman A two-source extractor for polylogarithmic entropy. Exponential in a power of K at last — the first explicit construction in the right shape. | K = (log N)^O(1) N = 2^(K^Ω(1)) | yes |
| 2023 | Li Asymptotically within a lower-order factor of the coin flip. The constants are not written down, and for any k you might actually name, the coin flip still wins. | K = (log N)^(1+o(1)) the current record | yes |
Everything from 1981 onward is an asymptotic statement with constants nobody has written out, which is why only the two concrete curves are drawn. The honest summary is unchanged since 1947: name a k, ask for a colouring of a graph on 2^(k/2) vertices with no monochromatic k-clique, and no one can hand you one — even though almost every colouring works. See also: the ellipsoid gambit, where averaging over lattices proves dense packings exist in every dimension and no explicit lattice comes close.
Try it: At k = 30 the coin flip guarantees a good colouring on 272,717 vertices. The best thing you could actually print — the quadratic-residue graph — manages 900. The gap between what exists and what can be exhibited is the single most quoted open problem in the subject.
Once you have seen the move, you see it constantly. To show a graph with high girth and high chromatic number exists, take a random graph and delete the short cycles. To show good error-correcting codes exist, pick the codewords at random. To show there is a dense sphere packing in every dimension, average over a family of lattices and observe that the average is good — which is precisely Minkowski’s 1905 argument, and precisely as unconstructive. See also: the ellipsoid gambit, where randomising the order of a construction moved a bound that had stood for 78 years, and Breaking 4ᵏ, where the other end of the same inequality finally shifted in 2023.