An odd cycle is the only way to have none

The solution that was a losing set ended on a suspicion read off a single catalogue. Sixteen games on three positions, and the only one with no stable set is the one whose positions form a cycle of odd length. The graphs with too many stable sets have cycles of even length, and the graphs with exactly one mostly have no cycles at all. Three positions are not many to argue from. But a cycle can be taken alone, at any length, and there the pattern is immediate.

Going round an even cycle and taking every second position produces a set with no arc inside it, and each omitted position moves straight into a member. Taking the other half works equally well, and nothing else does, since any set with two consecutive members has an arc inside it and any set that skips two consecutive positions leaves one with no move into it. So every even cycle has exactly two stable sets. The argument on an odd cycle is the same except that it cannot close: alternating all the way round lands the last position next to the first, in the wrong phase, and there is no third option. So an odd cycle has none, at every length.

A reader might suppose this to be a fact about cycles, with nothing to say about a general graph, where vertices can have many moves and the cycles can interlock. Moses Richardson proved in 1953 that it is a fact about everything. His theorem, published in the Annals of Mathematics under the title Solutions of irreflexive relations and using the 1944 word in its title, says that a directed graph with no cycle of odd length has a stable set. Odd cycles are not one way among several for a game to have no stable set. On a finite graph they are the only way.

The construction, run on nine positions #

The proof is worth seeing, because it repairs exactly what went wrong when the peeling lost the end of play. On a finite game the argument started at positions with no moves. On a graph with cycles there may be no such position. What takes its place is a component nothing leaves: a group of positions, each reachable from each of the others, with no move out of the group. Every finite graph has at least one, because following moves must eventually get trapped somewhere. That gives the argument a floor to stand on, though a floor with a loop in it rather than a single position.

Pick any position in that component as a root. Everything in the component can reach it, so each position has a distance to the root: the fewest moves needed to get there. Now take every position at even distance. Two things need checking, and the second is the point of the whole theorem.

Every position at odd distance has a move to something one step nearer the root, at even distance, so it has a move into the set. That part is automatic, and it gives the absorbing half of the definition.

The set also has to be independent, and this is where parity comes in. Suppose two members u and w are joined by a move from u to w. From w there is a walk to the root of even length, so from u there is a walk of odd length, through w, to the root. But u is also at even distance, by a shortest walk of even length. And because everything is in one component, there is a walk from the root back to u, which has some length. Add it to each of those two walks in turn and the result is two closed walks through u, one of even length and one of odd. The odd one is a closed walk of odd length, and a closed walk of odd length always contains a cycle of odd length, which the graph was assumed not to have. So no such move exists. The hypothesis is used once, here, and it is used to say that the two ways of getting to the root cannot disagree about parity.

The rest is bookkeeping. Having taken this set, exclude everything with a move into it, and delete both. Whatever is left is a smaller graph, still without an odd cycle, and has a component nothing leaves. Repeat. Nothing later can spoil what is already chosen. A later member cannot move into a chosen one, since everything with such a move was excluded, and a chosen one cannot move to a later member, since nothing leaves its component. In the figure this takes four steps on nine positions, and the stable set it reaches is checked at the end rather than assumed.

When the graph has no cycles at all, each component nothing leaves is a single position with no moves, its only member is at distance nought, and the construction reduces to the peeling. It is the same argument with the end of play generalised, which is why the theorem feels like a repair rather than a new idea.

Checked on every game up to five positions #

A theorem does not need a census. What the census adds is the shape of what surrounds the theorem, because Richardson’s condition turns out to sit in the middle of a chain.

There are 9,608 different directed graphs on five positions, which is the known count, and a useful check that the enumeration is complete. On every one of them the search lists all the stable sets, and tests the rest. Of those 9,608, 1,544 have no odd cycle, and every one of the 1,544 has a stable set. All of the 612 that have no stable set have an odd cycle. The theorem has been proved since 1953, so that is not news. The interesting columns are the ones either side.

Going left, the 302 graphs with no cycle at all have a unique stable set, as the first of these essays said. Moving to no odd cycle multiplies the family by five, which is a large weakening of the hypothesis, and what it costs is uniqueness. A graph with an even cycle has a stable set but usually not just one: the two-way pair, drawn alone, has two. Absence of odd cycles buys existence; absence of all cycles buys existence and uniqueness. A game with no odd cycle and several stable sets is a perfectly good object with a question hanging over it, which is what those several sets mean, and the next essay answers that.

Going right, the column of Grundy labellings needs a word. A Grundy labelling of a graph gives each position a number equal to the mex of its moves’ numbers, the smallest not used by any move. On a game that ends it exists, it is unique, and it is the whole of the Sprague–Grundy theory. The positions labelled zero are a stable set, by the definition of mex: a zero position has no move to a zero position, and any other position has one. So a Grundy labelling is a stronger thing than a stable set. It contains one and it says more.

On a graph with cycles a labelling may or may not exist, and if it does it need not be unique. Yet the census says every graph with no odd cycle has one, all 1,544 of them, and this too is a theorem and a clean one. Removing the positions labelled zero from a labelling leaves a labelling, with every number reduced by one, of what remains. Conversely, a graph in which every part has a stable set can be labelled by peeling stable sets repeatedly: the first gets zero, the first of what remains gets one, and so on. And a graph with no odd cycle has no odd cycle in any part, so every part has a stable set. So the Sprague–Grundy function, the invention of 1935 and 1939, extends without any change at all from games that end to the whole of Richardson’s family. No loop-specific apparatus is needed there.

The chain is strict all the way along. On five positions, 410 graphs have a stable set and no Grundy labelling, and the first four of those appear at four positions. On all of them, every way of peeling stable sets off eventually reaches a remainder with none of its own.

How many a game can have #

The last column of the census records the most stable sets any one game has: two at two positions, three at three, four at four, six at five. That sequence has a recognisable source. If every move in a game can be reversed, so that each arc comes with its opposite, then the graph is really an undirected one, and independence and absorption together say exactly that a set is a maximal independent set: no two members adjacent, and nothing more can be added. Moon and Moser found in 1965 how many of those a graph can have, and the extreme graph is a collection of separate triangles, with a pair or a square making up the remainder, each triangle offering three independent choices. On five positions that is a triangle beside a two-way pair, three choices times two, which is six.

The census’s maximum matches that bound at all four sizes, so on these sizes no game with one-way arcs does better than the best game in which every move can be undone. Whether this continues is not settled by a table this short, but it gives the question of many stable sets a shape: the number grows exponentially with the size of the game, at about three to the power of a third of the positions, in the undirected family at least. A game of thirty positions can have tens of thousands of consistent standards of behaviour, by the very construction that gives Nim only one. Removing the cycles collapses all of that to a single set, and removing only the odd cycles collapses none of it, since those triangles of two-way arcs have odd cycles but a chain of two-way pairs, with none, still doubles the count with every pair. Uniqueness is therefore the thing that the end of play pays for separately, and existence is all that parity is able to buy.

The twelve smallest failures after the triangle #

Since the theorem says absence requires an odd cycle, it is natural to look at the absences directly.

The twelve on four positions are the twelve ways of adding a fourth position to the triangle without rescuing it, and the drawing shows how hard it is to rescue. A fourth position rescues the triangle only if it can sit in a set that the triangle’s positions are all covered by, and most ways of attaching arcs do not achieve that. Only one of the twelve has a decided position in it, and it is the isolated vertex, which is trivially a lost position with no effect on the triangle sitting beside it. On the other eleven every position is drawn.

That small observation turns out to be general and exact, and it will be the central claim of the next essay: a game’s stable sets are its lost positions together with a stable set of its drawn part. So the question of whether a stable set exists is entirely a question about the drawn part of the graph. Whatever the outcome labelling can settle plays no role in existence, and the odd cycle responsible for absence always lies among the draws.

The converse is false, and by a large margin #

The theorem has one direction. It would be tidy for a game with an odd cycle to have no stable set, and it does not work that way at all.

Of the 8,064 games on five positions that have an odd cycle, 7,452 have a stable set anyway, and only 612 do not. So of the 8,996 games with a stable set, 83 per cent have an odd cycle and owe the theorem nothing. Richardson’s theorem is correct and is nothing like a description of which graphs have stable sets. It is a sufficient condition that applies to one graph in six, and the majority of graphs with stable sets have them for some other reason.

The three-position catalogue already shows why. Take the triangle and add a single arc going backward along one edge, so that a pair of its positions now move to each other. Now that pair offers a choice, and one of the three positions can stand alone as a set, with each of the other two having a move to it. The odd cycle is still there and it no longer matters, because the graph has more than one route around it. For a stable set to be absent, the odd cycle has to be “unbroken” in a stronger sense, and no simple local description of that sense is known in general. This is the reason the question of which graphs have stable sets is much harder than the theorem makes it look. How much harder is a matter of record: deciding it is NP-complete.

There is a second kind of evidence that the odd-cycle condition is far from the truth, and it comes from a family of graphs no one would look at for this reason. Stable marriages are stable sets of a graph on pairs, and they always exist, by a theorem with nothing to do with parity. Nearly half of those graphs have odd cycles, and Richardson says nothing about any of them.

The convention, and what the arrow is doing #

The whole construction relies on what an arrow means, and the hypothesis is about directed cycles. A cycle of odd length in the undirected sense, whose arrows do not all point the same way, is no obstruction: a triangle with one arrow reversed has no directed cycle at all, and a unique stable set. So “no odd cycle” here is a claim about play and not about the board. A loop a play can actually go round is what matters, because the even-distance argument walks along moves.

The theorem also relies on finiteness, in a way worth flagging. An infinite graph with no odd cycle can still have no stable set: a single infinite path going one way has a stable set, but a graph of positions where each moves to all later ones has none, because any member would need nothing later to be in the set and everything after it would need a later member. Later work on this has had to add a condition, usually that each vertex has finitely many moves, and even so an infinite ray can take the odd cycle’s place as an obstruction. The positions of any game drawn here are finite, and that is the condition being used when the first step relies on a component nothing leaves.

What the census cannot say #

Anything past five positions. The census is exhaustive to 9,608 graphs and no further, and the proportions in it are small-graph proportions. The odd-cycle share of the stable-set graphs should grow with size, because a graph with many arcs almost always has an odd cycle, but that is an expectation and the count does not establish it. Nor does the table say whether the share of graphs with a stable set at all stays high: it goes from 94 per cent at four positions to 94 per cent at five, and two points do not make a trend.

How the counts continue. The maximum of six on five positions matches Moon and Moser’s bound for undirected graphs, and nothing here proves that a game with one-way arcs cannot beat that bound on more positions, or says how the typical number of stable sets behaves as games grow.

Why any given graph with an odd cycle has a stable set. The search that finds one gives no reason beyond the set itself. Richardson’s construction gives a reason, and it gives one only on graphs where the theorem applies. For the 7,452 graphs on five positions outside his family, the census offers a verdict and no explanation.

Whether Richardson had games in view. He writes of irreflexive relations and borrows the 1944 word. That Grundy labellings extend to his family and that all of this is a statement about games is clear now and was clear to Berge in the following decade. Nothing here establishes what Richardson himself took his theorem to be about.

Still open: what an extra solution is for #

The first essay asked what could replace the bottom of the graph, and Richardson’s answer is a component nothing leaves, with parity doing the work that the end of play did. The theorem pays for that replacement in uniqueness. On a finite game the single stable set has a meaning, since it is the lost positions. Beyond that, a graph with no odd cycle usually has many stable sets, and the same positions may be in one and out of another. The outcome labelling has already said what it can: on a two-way pair, both positions are drawn, and it has no way to tell them apart. So either these extra stable sets are a mere artefact of a definition taken too far, or they are saying something about draws that a three-way label cannot. The question is what a stable set knows about a draw, and it has a surprisingly exact answer.