Invite some people to a party. Any two of them either know each other or do not, and you get no say in which. The asks for the smallest number of guests that forces a group of three who all know each other, or a group of three who are all strangers. That number has a name, and the interesting part is how few of them anybody has managed to compute.
Six guests are enough, and the next cases get out of hand fast. The gives the minimum number of guests needed so that at least some will all know each other or at least some will all be strangers. Ramsey’s theorem guarantees such a number always exists. For three and three it is six. For four and four it is eighteen, for four and five it is twenty-five, and for five and five nobody knows.
The Ramsey number gives the solution to the party problem. That problem asks the minimum number of guests who must be invited so that at least some given number will know each other, or at least some given number will not. Put in the language of graph theory, it is the minimum number of vertices such that every undirected simple graph of that order contains a of one order or an independent set of another.
Ramsey’s theorem states that such a number exists for every pair of sizes. That is a strong guarantee and it comes with no method attached: knowing an answer exists and knowing what it is are entirely separate problems here.
The famous case is three and three, where the answer is six, established by Greenwood and Gleason in 1955. The same work gave three and four as nine and three and five as fourteen. Later results filled in three and six as eighteen, three and seven as twenty-three, three and eight as twenty-eight, and three and nine as thirty-six. For four and four the answer is eighteen, and for four and five it is twenty-five.
Then the list stops. The exact value for five and five is not known, and work on it has consisted of narrowing bounds rather than settling the number. A is what shows that a given count of vertices does not suffice, and constructing them turns computationally hopeless as the sizes grow. MathWorld is a reference work rather than a paper, and the page also carries very recent bounds and machine-assisted claims whose independent verification it flags, so this card rests on the classical exactly known values.
wat. Six people at a party force three mutual friends or three mutual strangers, and for five and five the answer is still unknown.
wat wat
It is a rare case where existence is easy and computation is brutal. Ramsey’s theorem proves the number is always there, and finding it for five and five has defeated everyone for seventy years.
How do we know?
Wolfram MathWorld states the party problem, its graph-theory formulation in terms of cliques and independent sets, Ramsey’s theorem, and a table of the exactly known values with their original references.
What is still unknown
MathWorld is a reference work summarizing results rather than a paper, and the page also carries recent bounds and machine-assisted claims whose verification it notes separately. The card uses only the classical exactly known values.
Learn something?
Where to next
What can you prove by counting boxes?combinatorics
Did Alan Turing really prove the halting problem attributed to him?proof
Why is there always one point in the coffee that did not move?proof