A pairing that changes once

In the switching game on points, Short claims points and Cut deletes them, and Short wins once a route from A to B runs through claimed points only. The plainest proof that Short wins moving second is a pairing: a set of disjoint pairs of points such that every smallest set of points cutting A from B holds a whole pair. Short answers each deletion by claiming the deleted point’s partner, Cut can never delete both points of a pair, and so Cut never completes a cut. Two neighbours keep a pairing found that such a certificate exists for every Short win on every graph of seven points, and for every win sampled in the link game, and then found where it stops. At ten points with three neighbours each, a cubic graph is a win for Short whoever moves, and none of its 764 pairings holds all ten of its cutting sets.

That essay closed on the certificate question. The full game tree certifies the win, since a tree that answers every line of Cut’s play is a proof by exhaustion. But a tree is a poor certificate. It has to be carried whole, and checking it means replaying it. The question was what the next plainest kind of certificate is, and it named two candidates: a pairing that may change once, and a pairing on a slightly larger graph, the device the first move is a link that is not there used for the link game. The first one works, and in a way that turns out to contain the second.

One claim, then a pairing #

The certificate this essay measures has a shape that can be stated in a line. Short answers Cut’s first deletion with a stated claim, chosen after seeing the deletion, and from then on answers by a fixed pairing of the points that are left. The pairing has to hold the cutting sets of the position after that first exchange, with the deleted point gone and the claimed point already Short’s. A plain pairing is the same thing with no exchange first. Call that the certificate of nought changes, and this one the certificate of one change. More generally, a certificate of $k$ changes answers Cut’s first $k$ deletions by stated claims and only then settles into a pairing.

On the cubic graph a certificate of one change exists. Whatever Cut deletes first, Short has a claim after which a pairing of the remaining points holds every cutting set. It can be written as a table of eight rows, one per opening, each a claim and a pairing. It can also be written more compactly, because one claim and pairing often serves several openings. Four such plans cover all eight, and the hero picture draws them. If Cut opens on e, f, g, i or j, Short claims h and pairs c with d. If Cut opens on d, Short claims c and pairs f with h, and that plan also serves e, g, i and j. If Cut opens on c, Short claims d and pairs e–f, g–i and h–j. If Cut opens on h, Short claims f and pairs c–g, d–i and e–j. That is four claims and eight pairs, and it is the whole strategy.

The table behind the plans says the certificate is not a narrow escape. Every opening has at least two claims followed by a pairing, and most have more. After Cut deletes i, a point that touches neither end, seven claims keep Short winning, and every one of the seven is followed by a pairing. Cut’s most dangerous openings are c and h, a neighbour of B and a neighbour of A. Each has only two claims that keep Short winning, and both of those happen to be followed by a pairing. The cubic graph does not need its answers to depend on the order of play for long. It needs one look at Cut’s first move and then nothing more.

Why one claim restores what the graph lacked #

A single plan shows why this works where a fixed pairing fails.

The cubic graph’s ten cutting sets include two small ones around the ends: A’s three neighbours e, f and h, and B’s three neighbours c, d and g. Delete all of either and that end is cut off. A fixed pairing has to put a whole pair inside both of them and inside the eight four-point sets through the middle as well, using at most four pairs among eight points. Two neighbours keep a pairing found that this cannot be done: some set is always left over.

Claiming h changes the problem. Once h is Short’s, A is no longer surrounded, because h is a claimed point beside A that Cut can never take. The set around A stops being a cut at all. What remains for Cut is to stop every route from h onward to B, and every such route passes through c or d. After any of the five openings this plan serves, every remaining cutting set contains both c and d, so the single pair c–d holds them all. Whichever of the two Cut deletes, Short claims the other. Claim c, pair f with h is the same plan from the other end: a neighbour of B claimed, two of A’s neighbours paired. The two openings those plans cannot answer are c and h themselves, since each deletes the point the plan wanted to claim. They need three pairs each, because once a neighbour of an end is gone the remaining cuts are spread more widely.

So the failure of the fixed pairing was never that the cubic graph is too tangled. A pairing must defend both ends at once, from the first move, and four pairs cannot do that here. One claim beside one end means only the other end needs defending, and one pair can defend it.

A tree against a table #

The value of a certificate is in what a reader has to carry, and here the difference is large.

The smallest winning strategy for Short, written as a tree, has one entry for every position at which Short must name a claim. Each choice is made to keep the rest of the tree smallest, and every one of Cut’s deletions has to be answered. It needs 68 decisions. The table of one claim and one pairing per opening needs eight claims and twelve pairs. The four plans need four claims and eight pairs, plus the note saying which openings each answers. Checking the tree means following every line. Checking the plans means listing the cutting sets after each opening and finding a pair inside each, which is what the cuts table above does for one plan in five rows.

The difference in kind matters as much as the difference in size. A tree is a machine’s object: it answers each position because it was searched, and nothing in it says why. A plan is a reader’s object. Claim beside one end, then guard the other end’s last two neighbours as a pair is a sentence, and it is the same kind of sentence as the diagonal pairing on Hex that three pairings and no order found, with one look at the opponent’s first move added.

Moving first, the pairing comes back #

The second candidate the lead named was a pairing on a slightly larger graph, the way the link game handles Short moving first by adding an imaginary link that Cut must spend its first move on. In the point game there is a simpler version of the same idea: Short moving first is Short moving second after a free claim.

On the cubic graph that free claim restores the plain certificate. Seven of the eight possible first claims are followed by a pairing that holds everything. Claim h and pair c with d, or claim c and pair f with h: one claim and one pair, the smallest certificate in this essay. Only claiming i, the point touching neither end, leaves a position no pairing holds, which fits the reading above. A claim helps a pairing by taking a neighbour of an end out of Cut’s reach, and i is no end’s neighbour.

This is where the two candidates meet. A certificate of one change for Short moving second is exactly a first-mover certificate on each of eight smaller graphs. After Cut deletes a point, the position is the cubic graph with that point removed and Short to move, and the plan is one claim followed by a pairing, the first-mover certificate of that smaller graph. The pairing that changes once is the link game’s imaginary first move, applied after every opening Cut could choose. The first move is a link that is not there found that device deciding every subgraph of seven link-game graphs. In the point game it does the same work one move later.

One change, nearly always #

The cubic graph is one example, and one example of a certificate is a curiosity. The seeded samples that found it found others: every graph of eight to twelve points drawn there that Short wins moving second with no pairing. Each can be asked the same question.

There are 23 of them, on nine to twelve points, with three, four or five neighbours to a contested point. Twenty-one are certified by one change. Two need a second, and both are on eleven points with at most four neighbours. None needs three. Within the range the samples reach, then, the step from a fixed pairing to a strategy that has to be searched does not pass through a long sequence of increasingly adaptive certificates. It is one step, nearly always.

The two exceptions are not much of an exception.

Each has exactly one opening that a single change cannot answer, and in both it is Cut deleting a neighbour of A. After it, exactly one claim keeps Short winning. Every other claim loses, so the claim is not a choice, and from that forced claim a certificate of one change follows. The second change is spent on a move a player would make without being told, because it is the only move that does not lose. Counting a forced claim as no decision, all 23 pairless wins in the samples are certified by a pairing that changes once.

Lehman’s trees change at every move, and need not #

There is an older strategy in this subject that changes its answer constantly, and setting it beside the plans says something about what “adaptive” is worth. In the link game, where Short secures links and Cut deletes them, Lehman’s theorem says Short wins moving second exactly when the graph holds two spanning trees with no link in common, and a winning strategy that is a spanning tree drew the strategy that follows from it. When Cut deletes a link of one tree, Short secures a link of the other tree that reconnects it, and then rebuilds the two trees around the change. The partner of each link is decided only when that link is cut, and it depends on everything cut before. Taken literally, the strategy changes at every move.

Yet every link-game win in the samples two neighbours keep a pairing drew also has a fixed pairing of links that meets every cut: a certificate of no changes at all. The tree strategy is adaptive in its description and not in its need. Re-deriving the answer at every move is one way of carrying a strategy, and on those graphs a fixed list would have done as well. The cubic graph is the first object in this sequence where the need is genuine: no fixed list exists, and one look at the opponent’s first move is the least adaptivity that works. The scale that matters is how much a winning strategy has to look, not how much a given description happens to look. On that scale the link game sits at the bottom, needing no look at all, the cubic graph one step up, and the census puts every pairless win it found on that same step once forced claims are set aside.

That reading also says what cut is Short on another graph bought for the link game. Its duality turns Cut’s game into Short’s game on the dual graph, so a certificate for one player is a certificate for the other, and both are trees. Nothing comparable has been found for points. Cut’s side of the cubic graph is simply a loss, and the certificate of one change is a statement about Short alone.

The convention the counts depend on #

Shannon’s game on points, as in the essays before this one. A and B are fixed and never joined directly. Every other point is contested. Short claims, Cut deletes, and Short wins once claimed points complete a route, Cut once no route survives. “Moving second” means Cut deletes first. A cutting set is minimal when no point can be dropped from it. A certificate of $k$ changes is checked by recursion: after each of Cut’s possible next deletions, some claim must leave a position that has a certificate of $k − 1$ changes. A certificate of nought changes is a pairing that holds every minimal cutting set of the position, counting the claimed points as Short’s and leaving the deleted ones out. “Forced” means the claim is the only one that keeps Short winning, decided by solving the position outright. The strategy tree counts one decision per position Short must answer, positions reached in different orders counted once.

What the counts cannot show #

Anything beyond the samples. The 23 pairless wins are what seeded random graphs of eight to twelve points produced, up to four thousand draws to a cell. They are not every pairless win of that size, and a graph needing two unforced changes may exist at eleven points and not have been drawn.

That one change is the plainest possible certificate. Other shapes were not tried. A pairing that changes on a stated event later in the game, or a pairing of pairs, might certify some graphs more compactly still, and the comparison above is between this shape, a plain pairing and the tree, not against every certificate there could be.

And a sentence for every plan. Two of the cubic graph’s four plans read as sentences, claim a neighbour of one end and pair the other end’s remaining neighbours. The plans for openings c and h use three pairs each, and nothing here says what those pairings are protecting in words.

Why no fixed number of changes can be enough #

The census suggests that a pairing that changes once, perhaps after a forced claim, certifies every win. It cannot be true of every graph, and the reason is a fact about how hard the game is, not a further sample.

How hard is it records where the general game sits. Shannon’s game on points, on arbitrary graphs, is the game Even and Tarjan showed in 1976 to be complete for the class of problems solvable in polynomial space. A certificate of a fixed number of changes, $k$, is short: its table has one entry for each sequence of $k$ deletions, a number polynomial in the size of the graph, and each entry is a claim and a pairing. Checking a pairing asks whether any choice of one point from each pair, with the unpaired points, lets Cut separate A from B, and that is a question with a single universal quantifier. So if every win had a certificate of $k$ changes, deciding who wins would take one guess and one universal check, which puts it at the second level of the polynomial hierarchy, well below polynomial space. Unless those classes coincide, which is not believed, some graphs need more changes than any fixed number, and the number has to grow with the graph.

That makes the census’s finding a statement about where the growth begins rather than whether it happens. On graphs this small the adaptivity a strategy needs is one look at the opponent’s first move. Somewhere larger, a strategy must look further before it can settle, and further again on larger graphs still. Hex, the planar instance that a point with three neighbours placed at six neighbours, is itself complete for polynomial space, so the same is true of Hex boards as they grow, and the diagonal pairing on boards of $n$ rows and $n + 1$ columns is a family on which the growth is postponed for ever.

Still open: the first graph that needs two real changes #

The two graphs in the census that needed a second change spent it on a forced claim. The question that marks where the growth starts is the first graph whose certificate needs two changes neither of which is forced: a win in which Short must look at Cut’s first move, choose among several claims that all keep winning, look again, and only then settle into a pairing. The census at eleven and twelve points has none. The measurement is the same recursion run over every graph of eight and nine points rather than a sample, which is the size at which the first pairless wins appear. If the smallest such graph is much larger than the smallest pairless one, the steps up that scale are spaced out. A plain pairing first fails, in the samples, at nine points, one change at some larger size, two at a larger one still, and the spacing is a measurement of how quickly the switching game’s hardness arrives on graphs small enough to draw.