Ramsey's theorem — order out of chaos

What just happened?

We joined every pair of people with a line and coloured it in two colours: blue = “they know each other”, red = “they don’t know each other”. For 6 people — no matter how we arrange the acquaintances — a monochromatic triangle always arises: either three people who all know one another, or three who are all strangers. For 5 people this can be avoided (the “pentagon + star” arrangement above).

Ramsey’s theorem (the party problem)

This is one of the most beautiful results in combinatorics, proved by the British mathematician Frank Ramsey in 1930 (in the paper “On a problem of formal logic”). Its most famous case: in any group of at least 6 people you will always find either 3 people who all know one another, or 3 who are all strangers — no matter who knows whom. Mathematically: colouring all edges of the complete graph $K_6$ in two colours always produces a monochromatic triangle ($K_3$).

This value “6” is the Ramsey number $R(3,3)$ — the smallest number of people guaranteeing a monochromatic triangle. We write the rule briefly as:

Why 6, and not 5?

For 5 people it is not guaranteed: the edges of the graph $K_5$ can be coloured so as to avoid a monochromatic triangle. The famous example is the “pentagon + star”: we set the acquaintances along a pentagon (a 5-cycle) and the non-acquaintances along the inscribed star (pentagram) — neither 5-cycle contains a triangle. This is exactly the arrangement you see on the stage for $n=5$. Only the sixth person breaks the symmetry: they have 5 connections, so at least 3 of them are the same colour — and among those three people a monochromatic triangle always closes up.

A deeper idea: chaos is impossible

The whole of Ramsey theory says something astonishing: complete chaos does not exist. In a sufficiently large structure some ordered pattern always appears, however hard we try to avoid it. Theodore Motzkin put it as: “complete disorder is impossible”. Ramsey theory has applications in computer science, number theory and logic.

A curiosity

Computing larger Ramsey numbers is so hard that the mathematician Paul Erdős joked: if aliens demanded the value of $R(5,5)$ under threat of destroying Earth, we should throw all the planet’s resources at the computation — but if they wanted $R(6,6)$, we had better try to destroy them first.

Why this matters for your exams:

The Ramsey number itself is a curiosity beyond the syllabus, but the move “people → vertices, acquaintances → colouring the edges of the complete graph $K_n$” is a textbook example of modelling in graph theory. Reasoning about an invariant (here: the unavoidable monochromatic triangle) and the pigeonhole argument at the “sixth person” are useful in advanced-level combinatorics problems.

Remember: in any group of at least 6 people there are always 3 who are mutual acquaintances or 3 who are mutual strangers — $R(3,3)=6$. Order cannot be eliminated entirely: a sufficiently large structure is always accompanied by some pattern.