Stable set — the series · Combinatorial Game Theory

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.

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.

part 1 · history

Parity on a cycle. Single directed cycles of two to seven positions. Even cycles have two stable sets, the alternating halves, one of which is filled; odd cycles have none.

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.

part 2 · history

A mirror where there was no solution. The sum of two cycles of 3 positions, drawn as a grid of pairs, with a diagonal filled. It is a stable set of the sum, although a cycle of 3 alone has none. Moves that wrap around are left out of the drawing.

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.

part 3 · history

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.

part 4 · history

Peeling a square by stable sets. A three-by-three square with lists of three colours per cell, coloured one colour at a time. In each panel the uncoloured cells wanting the colour are shaded and the stable set among them is filled and takes it.

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.

part 5 · history

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.

part 6 · complexity

Recording the turn doubles an odd cycle. On the left a cycle of three positions, which has no stable set. On the right the same game with the player to move recorded in each position, a cycle of six, with two stable sets, each consisting of all the positions with one player to move.

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.

part 7 · history

The one colour-blind stable set of Mū tōrere. All 33 classes of drawn position in Mū tōrere under rotation, reflection and colour exchange, each drawn as a small board from the viewpoint of the player to move, with the 16 classes of the unique stable set shaded.

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.

part 8 · history