Combinatorial Game Theory
who wins, and by how much
Concept

Odd cycle — where it appears

A directed cycle of odd length in a move graph, a loop play can go round that has no alternating half. Richardson's theorem of 1953 makes it the only obstruction: a graph with no odd cycle always has a stable set, though many graphs with one have a stable set too.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

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.

history · Stable set A stable marriage is a stable set. A three-by-three preference table with the pairs ranked by each side, shown three times. Each filled set of cells is a stable matching and also a stable set of the graph whose moves go from a pair to a pair one of its members prefers.

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.

history · Stable set 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.

history · Stable set 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.

history · Stable set

Named alongside it

The objects these essays reach for when they reach for this one.

Position graphStable setDrawExhaustive searchCertificateComplexityGrundy valueParityProofSymmetry

All concepts