Every game on three positions
All sixteen directed graphs on three vertices up to relabelling, each with one of its stable sets filled and the count written beneath. Nine have one, six have several and the 3-cycle has none.
6 essays call
stable-set. The drawing above is what it returns with no arguments at all; every
call below passes it something, because a placement that passes nothing draws whichever
member of the family the generator happens to default to rather than the one its essay argues
about.
Where it is called
Every one of these figures is a drawing of the same construction, so a correction to it corrects them all.
How it was found
The solution that was a losing set
In 1944 von Neumann and Morgenstern defined the solution of a game by two conditions on a set of outcomes: none overrules another, and each outcome outside is overruled by one inside. They were writing about coalitions. The same two conditions, read with a move in place of an overruling, describe exactly the lost positions of a game that must end. Where play can loop, the same definition gives several answers or none, and three positions are enough to show both.
How it was found
An odd cycle is the only way to have none
A cycle of two positions has two stable sets and a cycle of three has none. Moses Richardson proved in 1953 that this is the whole story of absence: a graph with no odd cycle always has a stable set. Run over all 9,608 games on five positions, the theorem holds without exception, sits inside a chain of five nested families, and leaves open the larger question its converse invites, since 7,452 of those games have an odd cycle and a stable set anyway.
How it was found
What a stable set knows about a draw
On a graph with cycles, outcome labelling calls a position lost, won or drawn, and stops. The stable sets go further in exactly one place. On every game of up to five positions they hold every lost position, no won one, and among the drawn positions are exactly the stable sets of the drawn part taken alone. So a stable set is a certificate that the player who keeps returning to it never gets stuck. It can distinguish draws that labelling cannot, and two parts with no stable set can have one between them.
How it was found
A stable marriage is a stable set
Draw a graph whose positions are pairs of people, with a move from a pair to any pair one of its members prefers. Its stable sets are exactly the stable marriages, on all 46,656 profiles of three men and three women. So Gale and Shapley's theorem of 1962 is an existence theorem of the kind Richardson's was, on graphs where 49 per cent have odd cycles and his hypothesis is useless. The reason it holds is that every clique in the graph is one person's list, and four roommates show what happens when it is not.
How it was found
The list that cannot run out
Give each cell of an n × n square its own list of n colours, and ask for a colouring from the lists with no repeat in any row or column. Dinitz asked in 1979 whether that is always possible, and reading the cells in order fails about four times in ten. Galvin's proof of 1994 needs one page. Use an ordinary Latin square to turn each row and column into a preference, so that every cell has exactly n − 1 moves, and peel off a stable set for one colour at a time. A list of n cannot run out against n − 1 moves.
What it costs
A formula drawn as a game
Backward labelling answers who wins on any finite graph in time proportional to the arcs. Whether the same graph has a stable set is another matter: Chvátal showed in 1973 that it is NP-complete, by drawing a formula as a game whose variables are two-way pairs and whose clauses are triangles. On every one of the 255 formulas of this form on three variables the graph has a stable set exactly when the formula is satisfiable, and every position is drawn. The hard question lies entirely where the easy one says nothing.
The whole library · The position index · The figures that play back