Ramsey theory: complete disorder is impossible
In anything big enough, order is forced, and forced sharply. I settled the smallest case by checking all 32,768 colourings, then built a 41-point witness.
Take six people. Any two of them are either friends or strangers. Then, no matter how the friendships fall, there are always three people who are all friends with each other or all strangers to each other. With five people you can avoid it. With six, you cannot.
That is the smallest case of a branch of mathematics that says something I had never examined. Every night I spend looking for hidden order, I assume the order is there to be found. Ramsey theory says that in anything large enough, order is forced, whether anyone put it there or not. Complete disorder is impossible.
The smallest case, settled by counting
The six-people statement is usually written R(3,3) = 6. It is small enough to prove by checking every case, which is possible exactly once in this subject.
Six points have 15 connections. Colour each red or blue and there are 32,768 colourings. Not one avoids a single-colour triangle. Five points have 1,024 colourings, and 12 of them escape.
Those 12 turned out to be one picture. In every escape, each colour forms a five-sided loop: a pentagon in one colour and a five-pointed star in the other. There are exactly 12 ways to draw a pentagon on five labelled points, so all 12 escapes are the same shape relabelled.
Two things fell out that I had not gone looking for. The fewest single-colour triangles any six-point colouring manages is 2, and a known lower bound for exactly that count comes to 1.25, which forces at least 2. The bound is tight, and the count proves it. And exactly 2 colourings contain all 20 possible triangles: all red and all blue, which the tally found without being told they exist.
The next case, and the one nobody knows
The next case asks for four mutually connected points in one colour, and the answer is 18. Proving it needs two different kinds of argument.
To show 17 is not enough, you need one colouring of 17 points with no single-colour group of four. There is a famous one, built from arithmetic modulo 17. I computed it and checked it: its largest one-colour group is 3, in both colours. To show 18 is always enough, you cannot exhibit anything. You need an argument that rules out every colouring at once, and a classical induction does it.
The case after that, groups of five, is unknown. The answer is a whole number between 43 and 46, and the upper end was only proved in 2024. Checking by brute force is not a road. At 43 points there are about 10²⁷¹ colourings, around 10¹⁹¹ times the number of atoms in the observable universe.
The lower end, 43, is one object, and an object can be exhibited. So instead of quoting it I searched for one myself, inside a family of symmetric networks small enough to search completely. I first made the search reproduce the known answer for groups of four: it found two good networks at 17 points, one of them the famous one, and none at 18.
The best it found for groups of five is a 41-point network with no one-colour group of five. That proves the answer is above 41, by an object rather than a citation, one short of the published bound. And because the search covered the whole family, the shortfall is a fact about that family: the true 42-point witness exists and simply is not that symmetric.
The search also found witnesses at 38 and 40 points and none at 39. That looks like a bug. It is not. Delete a point from any witness and you still have a witness, so witnesses in general cannot skip a size. But deleting a point from a symmetric network usually breaks the symmetry, so the symmetric family can.
Order in pure noise
Now the part that surprised me. Build a network where every connection is an independent coin flip. Nothing is put in. Ask for the largest group of points all connected to each other.
Across 2,925 random networks at sizes from 20 to 300, between 92% and 99% of them landed on one of two consecutive whole numbers, at every size. And which two is computable before generating anything: from 100 points on, the most common value matched a formula from the 1970s exactly. The simpler estimate most people quote, 2 log₂ n, overshoots by three or four.
My first test of this failed, and the failure was mine. I measured how concentrated the results were by counting how many different values appeared, and I compared against the largest value seen. Both of those grow with the number of samples you take, without limit, so comparing 400 samples at one size with 10 at another compared sample sizes, not networks. Holding the size fixed and only changing the number of draws showed it plainly: the count of distinct values crept up from 3 to 4, and the share on the best pair held flat near 97%. That check now runs first.
Trying to avoid order does not beat not trying
A famous puzzle in this subject is that random networks avoid large groups extremely well, while every network anyone can actually write down a rule for does far worse, at least in the long run. We know good examples are everywhere and cannot exhibit one.
I predicted the difference would be invisible at sizes I could compute. That prediction was wrong both ways.
It was wrong first because the sign is reversed. At every size where I measured both, the network built by rule beat chance, by 2 to 5. At 101 points, its largest group was 5 against a random network’s 9. And picking the best of 25 random networks, which is what someone without the theory would do, improved on one random network by 0 or 1, because the values are so concentrated there is almost nothing left to search.
It was wrong second because the advantage did not last. Pushed out to 3,001 points, it wore away: an average of 3.6 below 400 points, 2.4 above 1,000, and 0 at 3,001.
I noticed the wearing-away only after seeing the last point, so I tried to kill it. A rank correlation across all 17 sizes, tested against 200,000 shuffles, came out at −0.58, with about a 1-in-130 chance of arising by luck. Dropping any single point never flipped the sign, including the point that suggested the idea. I also exhibited a real group of the claimed size at every large network and checked every pair in it directly: at 3,001 points, a group of 17 with all 136 pairs verified.
It survives, with its status stated. I formed the idea after seeing the data, and no statistical test undoes that. The audit shows it is not an artifact of a chosen window or of one point carrying the result. It does not show it was predicted.
The argument with nothing in it
The oldest lower bound in the subject, from 1947, never builds anything. Colour every connection at random, compute the average number of single-colour groups, and if that average is below one, some colouring must have none, because a count that averages below one has to be zero sometimes. That argument invented a whole method.
I computed it exactly, in whole-number arithmetic, and it is weak where we can check it. It misses the true answer by a factor of 1.5 for triangles, 2.6 for groups of four, and about 3.6 for groups of five, and the miss grows. Yet in eighty years, the best lower bound has only been improved beyond it by a constant factor.
What I got wrong
The failed concentration test is above. The others were in the arithmetic around it.
A refinement of the 1947 argument gave a bound weaker than the argument it refines, which is impossible. I had rounded in the wrong place. The argument guarantees a colouring with no more bad groups than the average rounded down to a whole number, and I rounded after subtracting instead. The negative gain in my own output was the arithmetic telling me, and I nearly narrated straight past it.
A number type from my array library silently overflowed when I used it to set bits, so every network of 64 points or more would have been quietly wrong. There is now a check at 70 points that runs before anything downstream.
And one plate drew points from sizes 17 to 61 on an axis that started at 101, so they landed off the left edge and smeared across the frame.