Eighteen people, and the seventeen that escape

Among six people, three are mutual acquaintances or three are mutual strangers, and five is not enough. The proof that six suffices is one application of the pigeonhole principle; the proof that five does not is a pentagon, drawn once and checked by eye.

The next case is $R(4,4)$, and both halves get harder in different directions. The answer is eighteen.

The upper bound, by induction #

The argument that eighteen is enough generalises the one that six is, and it costs nothing extra.

Write $R(s, t)$ for the smallest $n$ such that any two-colouring of the pairs from $n$ things contains $s$ mutually joined in the first colour or $t$ in the second. The recursion is

$$R(s, t) \leq R(s-1, t) + R(s, t-1),$$

and the proof is one paragraph. Take $n = R(s-1,t) + R(s,t-1)$ points and fix one of them, $v$. The other $n - 1$ split into those joined to $v$ in the first colour and those joined in the second. If the first group had fewer than $R(s-1,t)$ members and the second fewer than $R(s,t-1)$, the total would be at most $n - 2$, which is one short. So one group is large enough.

Say the first is: it has $R(s-1,t)$ members, so it contains either $t$ mutually joined in the second colour — done — or $s-1$ mutually joined in the first, and adding $v$, which is joined to all of them in the first colour, gives $s$. Done either way.

With $R(3,4) = 9$ and $R(4,3) = 9$, the recursion gives $R(4,4) \leq 18$. And the argument used nothing but a count, which is why it generalises upward without difficulty and why the bounds it produces are so poor: it gives $R(5,5) \leq 48$ against a true value known only to lie between 43 and 48.

Why $R(3,4) = 9$ #

The recursion needs its inputs, and the one it needs here is worth a paragraph because it is the smallest case where the two bounds do not meet automatically.

The recursion gives $R(3,4) \le R(2,4) + R(3,3) = 4 + 6 = 10$, using $R(2,t) = t$ — with two points wanted in the first colour, either some pair is joined in the first colour, or every pair is joined in the second and $t$ points are found at once.

Ten is one too many, and the improvement comes from a parity argument. If $R(s-1,t)$ and $R(s,t-1)$ are both even, the recursion can be tightened by one, because a graph on $R(s-1,t)+R(s,t-1)-1$ points cannot have every vertex meeting exactly $R(s-1,t)-1$ edges of the first colour — that would be an odd number of vertices each with an odd degree, and degrees sum to twice the edge count. So one vertex has a larger or smaller first-colour degree, and the argument goes through with one point fewer.

That gives $R(3,4) \le 9$, and an eight-point colouring with no monochromatic triangle and no monochromatic four completes it. The lesson is small and characteristic: the general bound is nearly right, and the last unit costs an argument of its own.

The lower bound, which has to be exhibited #

An upper bound is a proof that something must happen. A lower bound is a colouring in which it does not, and somebody has to produce one.

For $R(3,3) > 5$ the colouring is a pentagon and its diagonals: two five-cycles, one in each colour, neither containing a triangle. For $R(4,4) > 17$ a colouring of $\binom{17}{2} = 136$ pairs is needed with no four points agreeing in either colour, and searching for one at random is hopeless.

The construction that works is arithmetic. Label the points $0$ to $16$ and join two of them when their difference is a square modulo 17. The squares are $\{1, 2, 4, 8, 9, 13, 15, 16\}$ — eight of the sixteen non-zero residues, as always for an odd prime.

Two things have to be checked before this is even well defined. The rule must not depend on which way round the pair is taken, which needs $-1$ to be a square modulo 17 — and it is, since $16 = 4^2$ and $16 \equiv -1$. And the colouring must be balanced, which it is: eight of the sixteen differences are squares, so each point has eight edges of each colour.

That is the connection worth the whole rung. The pentagon that saves five people and the seventeen-point colouring that saves seventeen are the same construction at two different primes. What looked in the first essay like a lucky arrangement is one instance of a rule that produces good colourings whenever a prime is one more than a multiple of four.

Why the arithmetic works #

The reason a squares-based colouring avoids large single-coloured sets is a symmetry argument, and it is short enough to give.

The colouring is unchanged by adding a constant to every label, which is seventeen symmetries. It is also unchanged by multiplying every label by a square, because a square times a square is a square — another eight. So the colouring has at least $17 \times 8 = 136$ symmetries acting on 136 pairs, and it can be shown that they act transitively: every edge looks like every other edge, which is the same kind of statement as a solid all of whose corners are alike.

A colouring with that much symmetry cannot have a large single-coloured set in one place and not another, so any such set must be forced by the arithmetic rather than permitted by an accident of the arrangement. Checking whether a set of four exists then becomes a question about whether four residues can be found with all six differences square, which is a small computation.

The figure does not use that argument. It searches all $2^{17}$ subsets of the seventeen points, finds the largest with every internal pair one colour, and reports it — a direct verification with no theory in it, which is the appropriate check for a claim that a particular object has a particular property.

The two arguments are different in kind #

It is worth separating them, because the difference is the whole character of the subject.

The upper bound is non-constructive. It says that in any colouring of eighteen points a monochromatic four exists, and it gives no way of finding one — the induction locates a large group and recurses, but at each stage the “large group” is whichever one happens to be large, and following the argument on an actual colouring is a search.

The lower bound is fully constructive. The colouring can be written down in a line, checked in a second, and handed to anybody.

That asymmetry runs through the whole of Ramsey theory. The upper bounds are counting arguments and the lower bounds are constructions — except at larger sizes, where the best known lower bounds are not constructions at all but probabilistic arguments that no colouring anybody has ever seen achieves, which is the next rung.

What eighteen means as a statement about people #

The theorem’s usual phrasing is worth taking seriously for a moment, because the numbers are small enough to be about something.

Among eighteen people, there are four who all know one another or four who are all mutual strangers. Seventeen is not enough: an arrangement of acquaintance among seventeen people exists in which no four are mutually acquainted and no four are mutual strangers.

Nobody has ever met such a group of seventeen, and the reason is worth stating: the arrangement is extremely rigid. Each person must know exactly eight of the other sixteen, the pattern of who knows whom must be the arithmetic one above or something isomorphic to it, and any small perturbation destroys the property. Real acquaintance graphs are nothing like it — they clump into groups who all know one another, which produces monochromatic fours immediately.

So the theorem is sharp in a way that is invisible from the phrasing. Eighteen is where the worst case runs out. The typical case ran out at about six, and every real group of ten has several mutually acquainted fours in it. The subject’s interest is entirely in the extremes, and its numbers describe an adversary rather than a population.

Where the numbers stop #

$R(3,3) = 6$. $R(4,4) = 18$. $R(5,5)$ is unknown.

That is not a statement about proof techniques being unavailable. $R(5,5)$ is a finite question: check every two-colouring of the pairs from $n$ points for each $n$ between 43 and 48, and the answer falls out. The number of colourings of the 946 pairs among 44 points is $2^{946}$, which is beyond enormous, and the symmetry reductions that make such searches feasible reduce it by nothing like enough. The searches that settled $R(4,5)$ worked instead by growing colourings vertex by vertex and pruning, which is an exhaustion of a different shape — and even that has never come close on the next case.

Erdős’ remark on the subject is the standard quotation and it is worth repeating because it is precise about the two scales. If an alien fleet demanded $R(5,5)$ or Earth would be destroyed, humanity should put every computer and mathematician on it and would succeed. If they demanded $R(6,6)$, humanity should attempt to destroy the aliens.

What is known, and what the table looks like #

The exact values known are few enough to list. $R(3,3)=6$, $R(3,4)=9$, $R(3,5)=14$, $R(3,6)=18$, $R(3,7)=23$, $R(3,8)=28$, $R(3,9)=36$, $R(4,4)=18$, $R(4,5)=25$. That is essentially the whole table, and $R(4,5)=25$ was settled in 1995 with several years of computer time.

The growth is at least exponential and at most exponential with a different base: $2^{k/2}$ below and $4^k$ above, and closing the gap between those two bases is one of the older open problems in combinatorics. A 2023 result improved the upper bound to $3.99^k$, which was a substantial event and moved the base by one hundredth.

The gap between what is built and what exists #

Two numbers are worth putting side by side, because they say what the subject’s central difficulty is.

The best explicit colourings — ones anybody can write down — show that $R(k,k)$ grows at least like $k^{c\log k / \log\log k}$, which is faster than any polynomial and far slower than any exponential. The best colourings proved to exist show growth like $2^{k/2}$.

Those are not close. For $k = 30$ the explicit constructions give a few thousand and the existence proof gives about thirty thousand; by $k = 100$ the gap is many orders of magnitude. Nobody has ever seen a colouring as good as the ones randomness proves are there, and the problem of producing one has been open since 1947.

That gap is not a curiosity of this one problem. It is the standing situation wherever the probabilistic method applies: a proof that good objects are plentiful, and no way of naming one. The next rung is about the proof; the gap it opens is the reason this rung’s Paley colouring — an object one can actually hold — is worth as much attention as it gets.

What the picture cannot show #

The hero figure draws 136 edges among seventeen points, which is at the limit of what can be read. The claim it supports — that no four points agree — is a statement about $\binom{17}{4} = 2{,}380$ quadruples, and a reader cannot check even one of them from the drawing without tracing four edges through a thicket.

So the figure is doing something more modest than proving its caption: it shows that a rule exists, that it produces a definite colouring, and that the colouring is symmetric enough to be believable. The verification is the exhaustive search the caption reports, which happens off the page.

And nothing here can show the upper bound at all. Eighteen points would be 153 edges, and the claim is about every one of the $2^{153}$ colourings.

What the recursion does not know #

One more remark about why the upper bound is so poor, since the rung has spent most of its length on the lower one.

The induction takes a point, splits the rest by the colour of their edges to it, and recurses on whichever half is large enough. It uses exactly one fact: that the two halves cannot both be small. Everything else about the colouring is discarded — how the edges within each half are arranged, whether the two halves are joined to each other in any structured way, whether the point chosen was typical.

Discarding that much is what makes the argument work for every $s$ and $t$ at once, and it is also why the answer is so far out. An argument that consults nothing but a count cannot distinguish a colouring designed to resist it from a random one, and the designed colourings are the ones that determine the truth.

Every improvement to the upper bound in eighty years has come from consulting a little more: counting the edges within the halves, using the parity trick that saved a point in $R(3,4)$, and — in the 2023 improvement — tracking how the recursion’s two branches overlap. The gains have been real and small, which is what happens when a bound is loose for a structural reason rather than a technical one.

The ladder from here #

Rungs above: the probabilistic lower bounds, and the colourings they prove to exist without producing. Ramsey’s theorem on the number line, where the structure forced is arithmetic rather than graphical. Sequences that cannot avoid a long climb or a long fall. The infinite version, which is easier than the finite one. Graph Ramsey numbers for sparse graphs, where the answers are known and linear. And the constructive gap: the best explicit colourings against what randomness proves exists, which is a chasm.

What a lower bound is #

The rung’s lasting point is a distinction about evidence.

To prove that something must happen, count. To prove that it need not, build. The first kind of argument scales — the induction above works for every $s$ and $t$ — and gives bounds nobody believes are tight. The second kind does not scale, requires an idea per case, and gives exactly the truth about the case it addresses.

The Paley colouring is a good lower bound because it is arithmetic: the property that makes it work is a fact about squares modulo a prime, which is the same subject that decides which numbers are squares in the first place. A combinatorial question was answered by a construction from number theory, and that is the pattern in essentially every good explicit Ramsey colouring known.