Stable set — where it appears
Named by 8 essays across 2 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
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.
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.
Taking turns removes the hard part
Whether a graph has a stable set is NP-complete, and every hard instance depends on odd cycles. A real game's position graph has none. A position records whose turn it is and every move changes that, so all cycles are even, Richardson's theorem applies, and the set of all drawn positions with one player to move is a stable set of the drawn part, always. Mū tōrere and Three Men's Morris both confirm it. The hard question never reaches a game with turns, and the sets it hands over carry no information at all.
A rule that cannot see whose turn it is
The stable sets a game hands over work by telling the players apart. Forbid that, and read every board as mine and theirs, and the odd cycles come straight back. On Mū tōrere, with rotations and reflections identified too, the 892 drawn positions fall into 33 kinds, and among those there is exactly one stable set. It names sixteen shapes. A player who always hands the opponent one of them holds the draw against labelled play without knowing a colour, an orientation or an outcome, and the opening itself is one of the sixteen.
Named alongside it
The objects these essays reach for when they reach for this one.
DrawExhaustive searchPosition graphCertificateOdd cycleComplexityLoopyOutcome classProofSymmetryCounterexampleDisjunctive sum