Two neighbours keep a pairing, three lose it

A point with three neighbours found that the Shannon switching game played on points is the general game and the game on links its special case: the link game is the point game in which every contested point has exactly two neighbours, one at each end of the link it stands for. Lehman’s count of two spanning trees decides the link game. On points the count is gone — two graphs with the same points, the same links and the same number of separate routes can have opposite winners — and the general point game is the one Even and Tarjan showed as hard as any game of its kind. Hex is that game on a board whose contested points have six neighbours. The essay ended on the space between: somewhere between two neighbours and six, whatever lets a count decide the game stops existing, and nothing said where.

A count is one kind of certificate, and not the plainest. The plainest is a pairing: split the contested points into disjoint pairs so that every smallest set of points whose deletion cuts A from B contains both points of some pair. Short, moving second, answers each of Cut’s deletions by claiming its partner. Cut can never delete both points of a pair, so it never deletes a whole cutting set, so a route always survives. A pairing names every move Short will make before the game begins, and a reader can check it against the cutting sets without playing anything.

So the question can be asked in a form that has an answer on graphs small enough to search. At each number of neighbours, does every graph Short wins moving second have a pairing — and if not, where is the first one that does not?

Every graph of seven points #

Start where everything can be checked. On seven points, with A and B fixed and never joined directly, every other point contested and every set of links allowed, there are 971,104 graphs with at least one route from A to B. Each is solved exactly for Short moving second, and each is searched for a pairing: every way of splitting its five contested points into pairs, against every smallest cutting set.

At every degree, every graph Short wins moving second has a pairing. That is 1,556 wins among graphs whose busiest contested point has two neighbours, 36,140 at three, 166,492 at four, 198,975 at five and 55,461 at six — 458,624 wins, and not one needs anything but a fixed set of answers. In the other direction every pairing found wins, which is the argument above checked rather than trusted. The same is true of all 362 graphs of five points and all 13,880 of six.

The two-neighbour row is less than it looks. With every point contested and none owned, a graph whose contested points have at most two neighbours is a bundle of separate routes from A to B with some dead ends hanging off, and Short wins it moving second exactly when two of the routes have a single contested point each. That is the case the earlier essay’s pair of graphs turned on, and a pairing of the two middle points is its whole strategy. The link game proper needs the junctions of its graph to belong to Short already, which a census of contested points does not include. It is sampled separately, below.

What seven points say is narrower than it sounds and still striking. On small graphs, whatever their degree, the general point game — the one with no count — is won by the simplest certificate there is. Even and Tarjan’s hardness is a statement about families of graphs as they grow. None of it is visible at seven points.

The link game keeps it #

The link game is the point game with a contested point in the middle of every link and the original points handed to Short, so every contested point has two neighbours. Lehman’s theorem says Short wins it moving second exactly when the graph holds two spanning trees that share no link, and a winning strategy that is a spanning tree describes the play: whichever link Cut deletes from one tree, Short secures a link of the other that reconnects it.

That strategy is not a pairing. The link Short secures in answer to a cut depends on the two trees as they stand at that moment, and the trees are rebuilt after every exchange. Short’s answer to a given cut can differ from one game to another.

Yet every win in a sample of 2,816 has a fixed pairing of links as well. Random multigraphs of four to six points and six to twelve links, solved exactly; for each one Short wins moving second, every minimal set of links whose deletion separates A from B was listed and every pairing of links tried, and one always meets every cut in a whole pair. A separate run on larger multigraphs — five to eight points, ten to sixteen links — found 2,387 more wins, all with a pairing.

That is a measurement, not a theorem, and the tree strategy is no less correct for it. But it says something about the trees. The adaptiveness in Lehman’s strategy is a convenience of the proof: the answer can be read off the trees as they stand, which is easy to describe in general. On every graph sampled, a fixed answer would have done. Whether that is true of every graph that holds two trees is not settled here, and it is the kind of claim that a single larger graph could refute.

The first wins a pairing cannot explain #

Past seven points the census becomes too large to run whole, so the search turns to seeded samples: random graphs of eight to twelve points, with the number of neighbours any contested point may have capped at three, four or five. About 3,850 graphs a cell have a route from A to B, and two to three thousand of each are won by Short moving second.

At eight points there are none, at any cap. At nine, five graphs capped at four neighbours and one at five are won by Short with no pairing. At ten, four capped at three. From there they keep turning up, at one to five a cell, against two to three thousand wins each — a share of a fraction of a per cent. A pairing explains nearly everything at every size sampled, and it fails on the first graphs large enough to let it.

The cap of three matters most to the earlier essay’s question, and it is crossed. Graphs whose contested points have three neighbours each — the smallest number at which the point game is more than the link game — include wins that no fixed set of answers produces. So the plainest certificate does not survive any distance past two neighbours. It survives exactly at two, in every sample, and fails at three as soon as a graph has room.

A cubic graph, taken apart #

One of the ten-point graphs capped at three is worth reading closely. Every one of its ten points has exactly three neighbours, A and B included — a cubic graph — and Short wins it moving second and moving first. The labels below name the contested points c to j; A’s neighbours are e, f and h, B’s are c, d and g, and i and j touch neither end.

The graph has ten minimal cutting sets. Two have three points: A’s neighbours and B’s neighbours, since deleting all of either set isolates an end. The other eight have four points and run through the middle. A pairing of the eight contested points has at most four pairs, and each of the ten sets needs one of them whole. The search over every pairing finds that it cannot be done. There are 764 ways to pair some or all of the eight contested points; 26 of them leave exactly one set uncovered, the rest leave more, and none leaves nothing. Four leave all ten uncovered, the pairing with no pairs at all among them. In the pairing drawn — c with d, f with g, h with j — the uncovered set is {e, f, h}. Pair two of A’s neighbours instead and some set through the middle goes empty.

So Short has to win some other way, and the way is visible in its answers.

Every first deletion has winning replies, two to seven of them, and some come in mutual pairs: Cut deletes c and Short may claim d, Cut deletes d and Short may claim c. At the first move, a pairing looks possible.

The closest pairing shows where it stops being possible, in three moves. Cut deletes f, one of A’s neighbours, and Short answers with f’s partner g — a winning reply, as the table says. Cut deletes h, another of A’s neighbours. The pairing says claim j, h’s partner. The only claim that still wins is e, the last of A’s neighbours, because with f and h gone A has one way out left and Cut’s next deletion would take it. Answer by the pairing and Cut deletes e, and A is cut off with two claimed points elsewhere on the board. The pairing put h with j for good reasons — h and j lie together in three of the cutting sets through the middle — and those reasons are exactly wrong on the line where Cut attacks A instead.

The trouble, in general, arrives later than the first move, when the replies that still win depend on which points are already gone — a claim that was a good answer at the start is a wasted one once its route has been cut elsewhere. Short wins by keeping several routes alive and answering a deletion on one of them by strengthening another, and which other depends on the history. That is what a strategy looks like when the certificate for it is not a list of pairs.

Hex has six neighbours and a pairing anyway #

If degree decided whether a pairing suffices, Hex — six neighbours to every cell in the middle of the board — would be the last place to find one. It is one of the first. On a board of $n$ rows and $n + 1$ columns the player joining the nearer edges wins moving second, and a board one column wider shows the strategy is a pairing: each cell answered by its reflection across the diagonal, moved one column. Three pairings and no order counted the pairings that hold four by five and found three. Every second-player win in that family has a certificate of the plainest kind, at the highest degree a flat board allows.

So the number of neighbours is not what decides it. Hex’s cells have six neighbours and its cutting sets — the chains of the other player, read the other way round — are arranged by the geometry of a board that can be drawn flat, in a pattern a reflection can meet. The cubic graph has three neighbours to a point and cutting sets that overlap in a pattern no set of pairs can meet. What fails at three neighbours is not the degree as such but the freedom degree three already gives: enough links at each point for ten sets to share their points awkwardly. With two neighbours a contested point is simply a link, the cutting sets are the cuts of a graph, and on every graph sampled they never overlapped badly enough to defeat a pairing.

That also bounds what the census can say about the earlier essay’s question. Asked where between two neighbours and six the count stops existing, the measurement answers in a different currency: the plainest certificate holds at two in every case sampled and is lost at three, but it is not lost everywhere past three, and the boards people actually play keep it. The theorem that names no move is what Hex offers on the square boards, where the first player wins; on the boards one column wider it names every move, by a pairing, and the pairing is the reason those boards can be played perfectly by anyone who has read one sentence.

Why a pairing is the plain certificate and not the general one #

The pairing’s virtue is that it is checked, not played. Given a list of pairs and the cutting sets, a reader confirms the win by looking: does each set hold a pair? No game tree is searched. The cost is moved into finding the pairing, which on these graphs is a search over every way of pairing the contested points, and into listing the cutting sets, of which a graph can have many. A pairing is checked, not measured makes the same point about Hex on four by five, where finding the pairing took 1.6 million search nodes and checking it took 148 chains.

What the census shows is that, on small graphs, the plain certificate is enough. What the cubic graph shows is that it is not enough in general, and the reason is structural rather than a matter of size alone. Ten cutting sets with four pairs to cover them: when the sets overlap in the wrong pattern, no assignment of partners can put a pair in all of them, though a player who answers move by move can still keep a route open. A pairing is a fixed answer to a fixed set of threats. The general game lets threats be created in an order, and an answer can depend on the order.

There is also a difference in who can use each certificate. A pairing is something a person can carry to the board: Bridg-It, the board cut is Short on another graph identifies as its own dual, is won by a rule simple enough to print on the lid, and the diagonal pairing on Hex fits in a sentence. A strategy whose answers depend on the order of deletions has to be carried as a table or recomputed at every move, which is a machine’s way of playing rather than a player’s. On every graph of seven points the point game can be played perfectly by someone holding a list of two pairs; on the cubic graph of ten, nobody holding any list of pairs can play it perfectly, though the position is a win. That is the practical content of the finding, and it is a sharper line than the degree: it is the line between a game a reader can be told how to win and a game a reader can only be told is won.

The surprising part is where on the degree scale it happens. The link game — two neighbours, a strategy that is adaptive by construction — keeps a fixed pairing in every case sampled. The point game with three neighbours, which looks only a little richer, loses it. The adaptiveness that Lehman’s strategy has and does not need, the point game needs and does not have a theorem for.

The convention named #

Shannon’s game on points: Short claims a contested point, Cut deletes one, alternately; Short wins once claimed points complete a route from A to B, Cut once no route survives. “Short wins moving second” means Cut makes the first deletion. A cutting set is a set of contested points whose deletion leaves no route; it is minimal when no point can be dropped from it. A pairing is a set of disjoint pairs of contested points, and it certifies Short’s win when every minimal cutting set holds both points of some pair. The census counts labelled graphs, so isomorphic graphs are counted separately; the samples draw edges in a random order until a random number of them fit under the degree cap, with fixed seeds.

What the counts cannot show #

That the link game always has a pairing. Every win in the samples does, to sixteen links. A theorem would need an argument that turns two spanning trees into a fixed pairing of links, and none is offered here.

The smallest graph with no pairing. The census is exhaustive only to seven points; the first examples were found in samples at nine and ten. Somewhere at eight or nine points a graph with no pairing may exist that the samples missed, and the smallest cubic example may have fewer than ten points.

And how rare the failures stay. The share of wins with no pairing is a fraction of a per cent at every size sampled, and the samples are small. Whether the share grows with the graph, as Hex’s hardness suggests it must for some family, or stays a curiosity on random graphs, is not something a few thousand graphs of twelve points can say.

Still open: what a certificate for the cubic graph looks like #

The cubic graph is won, and no list of pairs proves it. Something shorter than the full game tree must, since the tree is a certificate of a kind, and the question is what the next plainest kind is. One candidate is a pairing that may change once — a fixed set of answers until a stated event, then a second fixed set — which is the shape Lehman’s trees would take if their exchanges were bounded. Another is a pairing on a slightly larger graph, the way the first move is a link that is not there handled Short moving first by adding an imaginary link. The measurement is the cubic graph’s game tree, compressed: the smallest set of rules of either shape that wins every line, and whether it is much smaller than the tree.