The colouring nobody has ever seen

The seventeen-point colouring that keeps $R(4,4)$ above seventeen is a construction: eight lines of arithmetic, checkable in a second. Nobody has produced anything comparable for $R(6,6)$, or for $R(k,k)$ at any $k$ past a handful.

What exists instead is an argument that good colourings are plentiful, which produces none of them. It was written down by Erdős in 1947, it is half a page long, and it founded a subject.

The count #

Colour each pair independently, heads or tails. Fix a set of $k$ points. All $\binom{k}{2}$ of its pairs agree in colour with probability $2\cdot 2^{-\binom{k}{2}} = 2^{1 - \binom{k}{2}}$ — the factor of two because either colour will do.

There are $\binom{n}{k}$ such sets. The expected number of them that come out single-coloured is therefore

$$\mathbb{E} = \binom{n}{k}\,2^{1 - \binom{k}{2}},$$

and that is the whole calculation. Expectation adds up whether or not the events are independent, which is the property doing all the work: the sets overlap heavily, their monochromatic-ness is nowhere near independent, and none of that matters to a sum of expectations.

The independence being used is worth pinning down, because it is easy to think more is being assumed than is. The pairs are coloured independently, by construction — that is the model. The events “this $k$-set is monochromatic” are wildly dependent on one another, and nothing in the calculation assumes otherwise. Expectation adds regardless, which is the property that lets the method work in situations where nothing else does.

The step #

If the expected number is less than one, then some colouring has none.

That deserves stating slowly because it is the entire method. The number of single-coloured sets is a non-negative whole number, and it has an average below one. A quantity that were always at least one would have an average at least one. So it is sometimes zero — and a colouring in which it is zero is a colouring with no monochromatic $k$-set.

Hence $R(k,k) > n$ for every $n$ with $\binom{n}{k}2^{1-\binom{k}{2}} < 1$, and estimating that gives

$$R(k,k) > \frac{k}{e\sqrt2}\,2^{k/2},$$

roughly $2^{k/2}$.

How bad it is small and how good it is large #

The figure prints the bounds the calculation gives: $R(4,4) > 6$, $R(5,5) > 11$, $R(6,6) > 17$. Against the known $R(4,4) = 18$ those are embarrassing.

They stop being embarrassing quickly. At $k = 20$ the probabilistic bound gives about 1,400 while the best explicit construction gives a few hundred. By $k = 40$ the probabilistic bound is about a million and the constructions are nowhere near. The bound that is useless at four is the best known at forty, and has been for nearly eighty years.

That is the surprising part, and it is worth being precise about what has and has not been improved. The exponential base has never moved: every improvement since 1947 has been to the polynomial factor in front. Lovász’s local lemma gains a factor of $k$; a more careful analysis gains a constant. The base is still $\sqrt2$, and the upper bound’s base was 4 until 2023 and is now about 3.99.

Where the exponent comes from #

The estimate is worth doing, because the $2^{k/2}$ is not obvious from the expression it comes out of.

Using $\binom{n}{k} \le (en/k)^k$ and $\binom{k}{2} = k(k-1)/2$, the expected count is at most

$$\left(\frac{en}{k}\right)^{k} 2^{1 - k(k-1)/2} = 2\left(\frac{en}{k\,2^{(k-1)/2}}\right)^{k}.$$

That is below one as soon as the bracket is below one, which is $n < \frac{k}{e}2^{(k-1)/2}$ — the bound quoted above, up to the constant.

The mechanism is a race between two exponentials in $k$. The number of $k$-sets grows like $n^k$; the chance of one being monochromatic falls like $2^{-k^2/2}$. The second is a much faster decay because its exponent is quadratic, so for $n$ up to about $2^{k/2}$ the second wins. The bound is where a quadratic exponent overtakes a linear one, and the square root in $2^{k/2}$ is the $k^2/2$ divided by the $k$.

Seeing it that way also explains why nothing has improved the base. Both exponentials are exact counts, not estimates; the only slack is in $\binom{n}{k} \le (en/k)^k$, which is tight enough that no rearrangement gains a factor growing with $k$.

The objection, and why it is not one #

The obvious complaint is that the argument does not produce a colouring, and the natural response is that it should be possible to extract one.

It is not, and the reason is a matter of arithmetic. The proof says that a random colouring works with positive probability, and inspecting that probability shows it is not merely positive: for $n$ somewhat below the bound, almost every colouring works. Good colourings are not rare — they are typical.

So a colouring can be found by picking one at random and checking. The difficulty is entirely in the checking: verifying that a colouring of $\binom{n}{2}$ pairs has no monochromatic $k$-set means examining $\binom{n}{k}$ subsets, which at $n = 1000$ and $k = 20$ is beyond any computation. The object is easy to produce and impossible to certify, which is a different situation from the one the complaint imagines.

That distinction recurs throughout the subject. The probabilistic method routinely produces objects that are common and unverifiable, and the search for explicit constructions is a search for objects whose properties can be argued rather than checked. That is exactly what the Paley colouring provides at seventeen points: its symmetry is an arithmetic fact about squares, so the property can be reasoned about rather than enumerated, and the enumeration is a confirmation rather than the proof.

What the calculation is really doing #

Stripped of the setting, the argument is the union bound wearing different clothes.

The chance that at least one of several events occurs is at most the sum of their chances. Here the events are “this particular $k$-set is monochromatic”, and the sum of their chances is exactly the expected count computed above. When that sum is below one, the chance that some event occurs is below one, so the chance that none occurs is positive, so a colouring with none exists.

Both readings are the same arithmetic and the expectation version generalises better, because it survives being pushed further: if the expected count is small but not below one, delete one point from each offending set and count what remains. That refinement — the deletion method — improves the constant, and it has no counterpart in the union-bound reading.

The dependence between the events, which would ruin almost any other argument, is entirely irrelevant to both. Two $k$-sets sharing $k-1$ points are monochromatic together far more often than independence would suggest, and the sum of expectations does not care.

An average that is not a typical value #

One more caution belongs here, because the argument’s step is easy to over-read.

The average is below one, so some value is zero is valid. The average is below one, so most values are zero is not, and neither is the average is above one, so most values are positive. An average above one is entirely compatible with the quantity being zero almost always and enormous occasionally — which is exactly what happens just above the crossing, where a few colourings contain vast numbers of monochromatic sets and pull the mean up.

So the method proves nothing above the crossing, and improving it means saying something about the distribution rather than the mean. That is what second-moment arguments do: computing the variance as well, and applying a bound on how far from the average a thing can be to show the quantity is often near its mean. Where those apply they give much stronger conclusions, and for this particular problem they have never given a better exponential base.

The asymmetry is worth remembering as a rule about expectations. A mean below one proves a zero exists; a mean above one proves nothing at all, and every attempt to use the second direction needs a variance.

Where else this goes #

The method is not about Ramsey numbers, and the three most striking applications are elsewhere.

Graphs with large girth and large chromatic number. It is intuitive that a graph with no short cycles should be colourable in few colours, since it looks locally like a tree. Erdős proved that graphs exist with no cycle shorter than any given length and chromatic number as large as desired. No explicit example of comparable strength is easy, and the construction is a random graph with an unlikely edge probability and a deletion step. That result is often the one cited as the moment the method became indispensable, because the conclusion is one nobody had been able to reach and one nobody expected — colouring a graph is supposed to be a local matter, and it turns out not to be.

Tournaments in which every $k$ players are beaten by somebody. Random tournaments have the property for $n$ large enough in terms of $k$; explicit ones are hard.

Error-correcting codes. The best known codes at many parameter settings are proved to exist by counting and have never been written down — the Gilbert–Varshamov bound is exactly this argument, and beating it explicitly took decades and algebraic geometry. That is the same gap this essay is about, in the subject where distance is a picture.

In each case the shape is the same: a property that seems to require careful design turns out to hold for a typical object, and the design problem is harder than the existence problem.

Why this was new #

It is worth being clear that the argument was resisted, because the resistance was not stupidity.

Before 1947, an existence proof in combinatorics meant a construction, and there was a reasonable position that a proof which produced nothing had not proved much. The counter-argument is the one made above: the probabilistic proof can be rewritten as a pure count of colourings, with no probability and no randomness anywhere, and nobody objects to counting. The randomness is bookkeeping.

What remained genuinely new was the style. The proof does not look at any colouring, does not construct anything, and reaches a conclusion about an object it has never described — and it does so by a calculation that takes half a page where any construction would take years and fail.

That the method then became the standard tool of an entire field, and produced results in graph theory, number theory, coding theory and computer science that nobody has matched by construction, is the retrospective answer to the objection. But the objection was about what a proof is for, and it has a residue: eighty years on, the objects this method promises still cannot be produced, and in several settings — cryptography among them — being unable to name the object means being unable to use it.

What the picture cannot show #

The figure plots the expected count, which is a smooth function of $n$, and the conclusion it supports is about a discrete object — a colouring — that the figure never draws. It cannot draw one, because the argument does not produce one, and that is not a limitation of the drawing.

What is drawn instead is the crossing point, and even that is slightly misleading. The curve is a continuous interpolation of a quantity defined only at whole $n$, and the bound is the largest whole $n$ below the crossing. Reading the crossing off the curve gives a fractional number that has no meaning.

And the figure’s logarithmic vertical axis compresses the very quantity that makes the argument work. At $n$ a little above the crossing, the expected count is enormous — for $k = 6$ and $n = 60$ it is around $10^{14}$ — which is a reminder that the method has an extremely narrow window. It says nothing at all above the crossing, and what it says below it is everything.

The window, and what sits either side of it #

It is worth summarising what the method establishes and where it says nothing, since the answer is unusually clean.

Below the crossing, the expected count is under one and a colouring with no monochromatic set is guaranteed. At the crossing, the expected count passes one and the guarantee stops — not gradually, but completely, because the argument’s only step was the comparison with one.

Above the crossing, nothing whatever is known from this argument. The expected count is large, which is consistent with every colouring having many monochromatic sets and equally consistent with most having none and a few having enormous numbers. The method’s silence there is total.

That is a narrow instrument and it is worth appreciating what it buys with so little. One inequality, applied once, gives a lower bound that has stood for nearly eighty years against every attempt to improve its exponential base — including attempts using far more sophisticated machinery. Sharpening the tool has not helped; what would help is a construction, and there is none.

The ladder from here #

Rungs above: the Lovász local lemma, which handles the case where the events are numerous but each depends on few others. The deletion method, and the second-moment arguments that go further. Ramsey on the number line, where the same counting works and the structures forced are arithmetic. Explicit constructions, and how far behind they are. And the algorithmic versions, which turn existence proofs into procedures and are one of the genuine advances of the last twenty years.

The shape of the argument #

To show something exists, average over everything and find that the average is favourable.

That is a strange way to argue and it is worth noticing why it is legitimate. Nothing about randomness is essential — the same argument can be phrased as a count of colourings, with no probability anywhere: the number of colourings containing a monochromatic $k$-set is less than the total number of colourings, so some colouring is not among them. The probability language is a convenience that makes the counting easy to organise.

What is essential is the willingness to prove existence without exhibition. That was a genuinely new move in 1947, and the resistance to it was real. The distinction between forced and exhibited that the first rung of this ladder drew is the same one, and the probabilistic method is what happens when a subject commits to the first half entirely.