The candidates a search throws away

A census is a claim that a list is complete, and completeness is the expensive half. Finding chains is easy; establishing that there are no others means visiting every candidate, and the number of candidates is where the whole difficulty lives.

The obvious version, and what it costs #

The straightforward enumeration has three steps.

First, list the degree sequences: how many pins each link carries, in non-increasing order, summing to twice the pin count with none below two. That is a small piece of arithmetic and it produces one sequence at four links, two at six, five at eight and eleven at ten.

Second, for each sequence, generate every graph with those degrees by choosing each link’s neighbours in turn.

Third, take each complete graph’s canonical form and keep it if the string has not been seen — the test the spectral shortcut was standing in for.

That works, and at eight links it generates 8,494 complete graphs to produce 71 answers — a hundred and twenty candidates for every answer. At ten links it does not finish: the ratio grows with the factorial of the link count, because the search is producing every labelling of every chain and the number of labellings of a chain with no symmetry is $n!$.

That is not a constant factor to be optimised away. It is the wrong shape of computation, and no amount of making the canonical form faster fixes it.

One rule #

The fix is a single test applied as the search runs, and it is a weak relative of the canonical form.

Suppose two links carry the same number of pins and sit next to each other in the ordering. Swapping them is a relabelling of the same graph. If the swap would make the adjacency string lexicographically larger, then the labelling currently being built is not the largest in its own class, and it can be abandoned — because the largest one will be reached down some other branch.

Two properties make it usable. It is sound: it only ever rejects a labelling that is not lexicographically maximal, and the maximal one is generated, so every isomorphism class keeps at least one representative. And it is cheap: comparing prefixes of two adjacency strings costs about as much as one row of the matrix, and it is applied after each row rather than at the end, so a bad labelling dies as early as it can.

It is not a complete canonicity test. Adjacent swaps generate all the relabellings within a degree class, but checking them one at a time does not decide maximality, so some classes keep more than one representative. That is why the canonical form is still taken at the end.

The combination is the ordinary shape of an exhaustive enumeration: a cheap partial rule that removes almost everything during the search, and an exact rule that finishes the job on what survives.

What the numbers become #

At four links: one candidate, one graph. At six: five candidates, five graphs — the rule does nothing at all, because there is nothing to prune. At eight: 92 candidates for 71 graphs. At ten: 3,000 candidates for 1,878 graphs, in about half a second.

The ratio of candidates to answers is now between 1.0 and 1.6 at every size, rather than growing without bound. That is the difference between a search whose cost tracks the size of its answer and one whose cost tracks the size of the symmetric group.

Where it stops #

Twelve links, and the honest account of it is a measurement rather than a decision.

A twelve-link chain of one degree of freedom has sixteen pins. The published figure for the number of such chains is 6,856. This routine does not confirm it: run at twelve links it does not return within ten minutes, and the reasons are three and they compound.

The search is larger. The candidate count has gone 1, 5, 92, 3,000, which is a factor of about fifteen to twenty a step; twelve links is somewhere in the tens of thousands to hundreds of thousands of candidates before anything else is considered.

The canonical form is larger. Refinement on twelve vertices leaves more classes to branch over than on ten, and the backtracking cost is not linear in the vertex count.

And the degeneracy scan is larger. Rejecting the graphs that hide a structure means counting every subset of the links: 1,024 subsets at ten links, 4,096 at twelve, for every candidate the search reaches.

None of that is a wall — it is a routine written to the size of the problem it was written for, and a better one exists. What this field claims is a census to ten links, computed here, agreeing with the published counts at every size it reaches. Twelve is named and not confirmed, which is the difference between a measurement and a citation.

Reading the rule in slow motion #

The pruning rule is short enough to be opaque, so it is worth watching it work on the smallest case where it does anything.

The search builds the adjacency matrix row by row. Row 0 is the set of links that link 0 is pinned to; row 1 is the set that link 1 is pinned to among the links after it; and so on. After each row, every pair of adjacent same-degree links whose rows are both complete gets the test.

Suppose links 3 and 4 both carry two pins, and the rows so far say that link 0 is pinned to link 4 and not to link 3. Swapping 3 and 4 would move that pin to the earlier position, which makes the string lexicographically larger at the very first place it differs. The branch is abandoned immediately — before rows 3 and 4 have been chosen at all, and therefore before the whole subtree beneath them has been explored.

That is where the saving is. The rule does not reject completed graphs; it rejects prefixes, and a prefix rejected at row 1 removes everything that would have been built underneath it. The eight-link search reaching 92 candidates rather than 8,494 is almost entirely that: the same graphs, cut before they were finished.

The corollary is that the rule does nothing at all on a chain whose links all have different degrees, because there are no equal pairs to swap. No such chain exists in these censuses — every assortment has at least four binary links — which is why the rule is worth having at every size.

Whether the answer can be trusted #

An exhaustive search that returns the expected number is a comfortable thing and comfort is not evidence, so it is worth being explicit about what has actually been established.

The count agrees with the published one at every size. 1, 2, 16, 230. That rules out a search that is missing whole assortments or over-counting labellings, and it does not rule out two compensating errors — a missed chain and a duplicated one — which would be invisible in a total.

The canonical form is checked by relabelling. Take a chain, scramble its labels forty times at random, and require the canonical form and the drawing to be unchanged. That is the check that catches a canonical form leaking its input’s ordering, which is the failure that would produce exactly the compensating pair above.

The degeneracy filter is checked by refusal. A ten-link graph is built deliberately with a triangle in it, and the filter is required to reject it and to name the triangle as the structure it found. A filter that has never rejected anything proves nothing, which is this site’s standing rule and is why the assertion exists.

And the enumerator is checked against a different subject. Asked for trees rather than chains — minimum degree one, one fewer pin than link — it returns 1, 2, 3, 6, 11, 23, 47, 106. That sequence has nothing to do with mechanisms and the routine was not tuned against it.

Why the pruning is the interesting part #

There is a general lesson here that the site has met before, and it is about where the cost of an exhaustive search actually is.

The instinct is that an enumeration is expensive because the answer is large. Usually it is expensive because the search space is quotiented by a group and the search does not know it — the same object is visited once for each element of the group, and the group is enormous. Ten links means a group of 3,628,800, so the overhead is not a factor of ten or a hundred; it is the reason the computation does not exist.

The repair is always the same in shape. Do not generate and deduplicate; generate only representatives, using a partial order that the group respects. Here that is lexicographic maximality within degree classes. In the algebra field it is following a root rather than re-solving. In the holding field’s escape enumeration it is enumerating extreme rays by subsets rather than sampling directions.

What the search does not do #

Two clarifications, because an enumeration that finishes invites more confidence than it earns.

It does not order the answers meaningfully. The census comes out in whatever order the degree sequences and the search branches produced, and the field re-sorts it by assortment and canonical form so that a chain’s index is stable across runs. That index is a convention, not a property: “chain 7 of the sixteen” means something only because the sort is fixed, and there is no natural ordering of kinematic chains.

And it does not check anything about mechanisms. The search produces graphs. Everything that makes a graph a mechanism — that it is connected, that no link carries one pin, that no subchain is a structure — is applied as a filter, and each filter is a separate piece of arithmetic that could be wrong on its own. The agreement with published counts at four, six, eight and ten links is the check on all of them together, and separately the same enumerator asked for a number from a different subject entirely returns the number of unlabelled trees.

That second check is the stronger of the two, because it is the one the routine was not tuned against. Reproducing 230 is evidence that the search agrees with the literature; reproducing 106 trees on ten vertices is evidence that it is enumerating graphs correctly, and the two failure modes are different.

The ratio is the measurement, not the seconds #

Half a second at ten links is quoted above and it is the least durable number in this essay. The quantity that carries the argument is the ratio of candidates to answers, and it is worth saying why, because it decides what to do next rather than merely reporting what happened.

A wall-clock time is a fact about a machine on a day. It halves when the hardware does, it changes with the language and the memory layout, and it says nothing about whether an enumeration will finish one size up — a search whose work grows by a factor of thirty per size is not rescued by a processor twice as fast. The ratio has none of those dependencies. It is a property of the algorithm against the problem, it is the same number on any machine, and it is the thing that decides whether the search is doing useful work or shuffling duplicates.

Between 1.0 and 1.6 at every size is very nearly output-sensitive: the search does an amount of work proportional to the number of answers, plus a small constant factor of waste. That is the best shape an exhaustive enumeration can have, and reaching it is the difference between a routine that scales with the census and one that scales with the labellings.

It also says where the next gain is not. A ratio already at 1.6 has at most 37% of its candidates left to remove, so no improvement to the pruning rule can win more than that — and the twelve-link difficulty is therefore not a pruning problem. The costs that grow there are the canonical form on more vertices and the degeneracy scan over more subsets, both of which are per-candidate costs that pruning does not touch. Knowing the ratio is what turns the search is too slow into the search is the right shape and two of its per-item costs are exponential, which is a different repair.

That is the general form of the lesson and it is worth carrying past this field. Measure an enumeration by its overhead ratio and its per-item costs separately, because they respond to different fixes and a single timing hides both. The eight-link search at 8,494 candidates for 71 answers was a ratio problem and a rule fixed it. Twelve links is not, and applying the same instinct there would spend effort on the one part of the routine that is already nearly optimal.

A census is not a database #

One more property of the arrangement, and it is a decision rather than a consequence.

The census is recomputed rather than stored. Every figure in this field runs the enumeration for itself; nothing is written down, and there is no table anywhere holding 230 adjacency strings. The result is remembered for as long as the figures need it and then discarded.

The reason is the one this site applies to every other quantity. A stored count can be right on the day it is written and wrong the day the filter changes, and nothing can see the difference; a computed one cannot be. It costs half a second per build, which is the correct price for a number that appears in eleven essays.

What a complete list is worth paying for #

It is worth closing on why any of this cost is justified, because the alternative — sampling, or working from the arrangements somebody happened to name — is much cheaper and is what the subject did for most of its history.

A complete list makes negative statements possible, and what it is then used for is a filter rather than a browse. There is no third six-link chain is not a statement any amount of sampling produces; neither is four of the eleven ten-link assortments contain no mechanism at all, nor these four chains have no closed-form driving choice. Every one of those is a claim about the whole of a space, and the whole of a space is exactly what an enumeration delivers and a search does not.

It also makes accidental findings possible. Nobody was looking for the two cospectral pairs; the polynomials were computed to build a bucketing filter and the totals came out two short. That kind of discovery is only available to a routine that visits everything, and it is the ordinary way an exhaustive computation earns back its cost. A sampled census would have had the same 228 distinct polynomials and no reason to notice that the number should have been 230.

The last thing worth saying about the cost is how small it is. The census is deterministic and it is a few hundred milliseconds, so recomputing it from scratch is cheaper than the bookkeeping that keeping a copy would need — which is the same discipline every other number on this site is under, and is the only arrangement in which a figure and the text beside it cannot drift apart.

There is a mild irony in the two numbers that is worth noticing. The pruning rule was worth writing because the ratio was 120 at eight links and would have been far worse at ten; having written it, the ratio is so close to one that the rule can never be worth improving again. A fix that works completely removes its own subject, and the useful consequence is that the measurement which justified the work is also the measurement that says the work is finished — which is rarer than it sounds and is the reason the ratio is quoted at every size rather than only at the size that motivated it.