Six people at a party

Six people are in a room. Every pair either knows each other or does not — no half-acquaintances, no ambiguity. Then some three of them are mutual acquaintances, or some three are mutual strangers.

That is true of any six people, whoever they are, however they came to be there. Nothing about the group is assumed.

The claim is a statement about all $2^{15} = 32{,}768$ ways of colouring the pairs, and it holds for every one of them. It is worth being clear that this is not a claim about typical parties, or about social clustering, or about anything to do with people. It is a fact about the number six.

The proof is one pigeonhole and a look #

Pick anybody — call them the first person. They have five relationships, each of one of two kinds.

Five things in two boxes forces three into one box. So the first person has at least three relationships of the same kind — say three acquaintances, though the argument is identical if it is three strangers.

Now look at those three people and the relationships among them. There are three such pairs.

If any one of those pairs are acquaintances, then those two plus the first person are three mutual acquaintances, and the claim holds.

If none of them is, then all three pairs are strangers, so those three are three mutual strangers, and the claim holds.

There is no third case. The proof is finished, and it consumed one application of the pigeonhole principle and one two-way split.

What deserves attention is the shape of the second half. It does not find the trio; it observes that both possible outcomes produce one. That is a proof by exhausting alternatives rather than by construction, and it is why the theorem tells nobody which three people to look at.

Five is genuinely not enough #

A theorem that says six suffices is only interesting if five does not, and five does not — there is an arrangement of five people with no such trio.

The arrangement is a pentagon. Adjacent pairs are acquaintances; non-adjacent pairs are strangers. Every triangle among five points uses two adjacent pairs and one non-adjacent, or one and two — never three of either — so no triangle is monochromatic.

That is a lower bound, and it is a different kind of object from the upper bound above. The upper bound is an argument about all colourings; the lower bound is a single exhibited colouring. One is a proof and the other is an example, and both are needed to pin the answer at exactly six.

The pentagon is also the reason the answer is six and not something else. It is the unique such colouring up to relabelling, which means five is not merely insufficient by a small margin — there is exactly one way to be lucky at five, and it does not extend.

Its structure is worth a second look, because the reason it works is a fact about five rather than a lucky arrangement. The two colour classes are a five-cycle and its complement, which is also a five-cycle — the pentagram — and five is the only number for which a complete graph splits into two copies of the same triangle-free graph. That self-complementary structure is why the counting comes out even, and it is the same kind of coincidence-that-is-not-one as the five regular solids: a small list, closed for an arithmetical reason, with nothing beyond it.

Adding a sixth person destroys it immediately. Whatever colours the five new edges are given, the pigeonhole step applies at that person, and the pentagon’s balance is exactly what leaves no room to absorb them.

The number, and how fast it becomes hopeless #

Write $R(s,t)$ for the smallest group in which either $s$ mutual acquaintances or $t$ mutual strangers are forced. The result above is $R(3,3) = 6$.

Ramsey proved in 1930 that $R(s,t)$ is always finite, which is the real theorem — every one of these questions has an answer. Finding the answers is another matter entirely.

$R(4,4) = 18$, settled in 1955. $R(5,5)$ is unknown. It is somewhere between $43$ and $46$, and it has been between $43$ and $49$ since 1995, with the upper bound creeping down and the lower bound unmoved since 1989.

It is worth being precise about why this is hard, because “unknown” usually suggests something is not decidable and here it is very decidable. $R(5,5)$ is a finite question: check every two-colouring of the pairs among $43$ people, and either find one with no monochromatic five, or prove none exists. The number of colourings is $2^{903}$, which is around $10^{271}$. Symmetry reduction and clever search cut that enormously and nowhere near enough. The universe holds about $10^{80}$ atoms.

So the obstacle is not depth but quantity, and it is quantity of a kind no improvement in hardware touches — the same situation as a proof that requires checking one thousand eight hundred configurations by machine, except that here the checking is $10^{190}$ times worse and no reduction has brought it into range.

Erdős put it best, and the remark is repeated because it is exactly right about the scaling: if aliens demanded $R(5,5)$ on pain of destroying the Earth, humanity should marshal every computer and every mathematician and would probably succeed. If they demanded $R(6,6)$, humanity should attempt to destroy the aliens.

What the theorem actually says #

The slogan is that complete disorder is impossible, and it is worth unpacking because it is easy to hear as mysticism.

The claim is not that structure is created from nothing. It is that a sufficiently large structure contains, unavoidably, a small ordered piece — and that this is forced by size alone, independent of how the large structure was built. Nobody put the triangle in. It is there because there is no room for it not to be.

That is a different phenomenon from the bell curve appearing from coin flips, where a shape emerges because averaging suppresses variation. Here nothing is averaged and nothing is typical: the conclusion holds for every colouring, including the ones deliberately constructed to avoid it. The pentagon shows what avoiding looks like, and the theorem says avoidance runs out.

The results in this family are numerous and all have that character. Any sequence of $mn+1$ distinct numbers contains an increasing subsequence of length $m+1$ or a decreasing one of length $n+1$ — Erdős–Szekeres, and its proof is the pigeonhole again, applied to a pair of counters. Any two-colouring of the whole numbers contains arbitrarily long monochromatic arithmetic progressions — van der Waerden. Any set of integers with positive density does too — Szemerédi, which is a much harder theorem and won a Fields Medal for its author’s methods rather than for the statement.

The method that came out of it #

The interesting legacy of Ramsey numbers is not the numbers. It is a technique invented to bound them.

Erdős, in 1947, wanted a lower bound for $R(s,s)$ — a colouring with no monochromatic clique of size $s$. Instead of constructing one, he counted. Colour every pair at random. The chance that a particular set of $s$ people is monochromatic is $2^{1-\binom{s}{2}}$. Multiply by the number of such sets and, if the total is less than one, some colouring must avoid all of them — because if every colouring had at least one bad set, the expected count would be at least one.

That argument produces $R(s,s) > 2^{s/2}$ in half a page, and it produces no colouring whatever. It is the first use of the probabilistic method, which is now a standard tool across combinatorics, and it is a purer form of the non-constructiveness that the pigeonhole principle already had: pigeonhole says a collision exists among things that have been listed; this says an object exists among things nobody has listed, on the grounds that a random draw would find one.

The bound has barely moved since. Sixty years of work improved the constant and not the exponent, and the best explicit constructions are still exponentially worse than the random one. That is a recurring and slightly humiliating pattern in the subject: random objects are better than any object anyone can describe, and describing one as good as a random one is often the open problem.

Where the small cases lie #

$R(3,3) = 6$ is small, memorable and thoroughly unrepresentative, and a reader who generalises from it will be wrong in every direction.

The proof at six is one pigeonhole step. The proof at $R(4,4) = 18$ is a substantially harder argument, and the verification needed a computer search. There is no proof of $R(5,5)$ at all. So the difficulty does not scale with the numbers; it scales with something that looks flat and is not.

The six also gives a misleading impression of the growth. $R(3,3) = 6$, $R(4,4) = 18$, $R(5,5) \ge 43$ — those look like a manageable sequence. The true growth is exponential in $s$, and known only to within an exponential factor. A reader extrapolating from three terms would guess wrong by an unbounded amount, which is the standing hazard of small cases and the reason this site has a theme about it.

What it costs, and where it is used #

Almost nothing here is computed, because almost nothing here can be. The applications are structural rather than numerical: Ramsey-type results are used to prove that some configuration must exist in a large object, and the proof then proceeds without ever locating it.

The one place the numbers themselves matter is in lower bounds for algorithms and data structures, where a Ramsey argument shows that any method must handle some unavoidable configuration and so must cost at least a certain amount. Those arguments are genuinely useful and they inherit the non-constructiveness: they say an adversary exists, not what it looks like.

One more use is worth naming because it is where these arguments meet the rest of this site. A great many statements of the form “a large enough structure must contain a pattern” are proved by finding the right thing to count and then applying a division — which is exactly the skill the pigeonhole principle demands, and exactly the skill that made throwing away everything except the adjacencies the right move in Königsberg. The theorem supplies the last line; choosing what to count is the work.

There is also a negative use worth mentioning because it corrects a common misreading. Ramsey theory is sometimes invoked to explain apparent patterns in data — constellations, conspiracies, coincidences — on the grounds that structure is forced in large enough sets. That is the right instinct and usually the wrong arithmetic: the sizes at which Ramsey bounds bite are astronomically larger than any data set, and the real explanation for coincidence in ordinary-sized samples is the birthday effect, which arrives far earlier and for entirely different reasons.

What the picture cannot show #

The K6 figures show three colourings out of $32{,}768$, and three drawings are no more evidence than one. What closes that gap here is unusual and worth being precise about: the space is small enough to exhaust, so the generator checks every colouring before drawing, and the assertion behind these figures is a proof rather than a sample. The first version of it sampled four hundred at random, which was weaker for no saving worth having.

That is available at six and at nothing beyond. At seven people the space is $2^{21}$, still fine; at the eighteen people of $R(4,4)$ it is $2^{153}$, and the exhaustive check that makes these figures honest is unavailable for every case except the one drawn.

The pentagon figure is in better shape, because a lower bound really is a single example, and the example is the whole content. That is the one figure here that proves what it shows.

Nothing here can show the scale. $R(5,5)$'s difficulty is a number with two hundred and seventy digits in it, and there is no drawing of $10^{271}$ that means anything. A figure of forty-three points and their nine hundred edges would be a black disc.

The ladder from here #

Rungs above: the pentagon’s uniqueness, proved rather than asserted. $R(4,4) = 18$ and the Paley colouring on seventeen points that gives its lower bound. Erdős–Szekeres, drawn as a sequence with its two counters. The probabilistic method as its own picture — the expected count, and the moment it drops below one. Van der Waerden’s theorem and the progressions. The happy ending problem, where points in general position force a convex polygon. Graph Ramsey numbers for sparse graphs, where the answers are known and linear. And the constructive gap: the best explicit colourings against the random bound, drawn on a log scale.

The unavoidable and the findable #

The lasting point is a distinction this essay has been circling.

There are two entirely different senses in which something can be known to exist. It can be exhibited — the pentagon, drawn above, is a colouring of five that anybody can check. Or it can be forced — the trio among six exists, and no argument in this essay produces one.

The second kind is cheaper to obtain and much harder to use. It is available from counting alone, which is why it arrives first in almost every area, and it hands over nothing that can be acted on. A very large amount of combinatorics consists of knowing that something is there and being unable to find it, and Ramsey theory is that condition in its purest form: a subject where the answers are finite, the questions are decidable, and the numbers are unknown and will stay that way.

The unusual thing about the case drawn here is that it sits on the boundary. At six the forced object can also be found — by inspection, and by the exhaustive check the generator runs — so both senses coincide and the theorem feels concrete. At eighteen only the forcing survives; at forty-three neither the forcing nor the finding is within reach, and the statement retreats to being a number known to exist between two bounds.

That progression, from a claim that can be seen to one that can only be argued to one that can only be bounded, is the honest shape of the subject, and six is the last place a picture can be drawn of it.