One gadget defeats every refinement

The game the algorithm was playing identifies colour refinement with a pebble game and exhibits the pair it fails on: a six-cycle and two triangles, which have the same number of points, the same number of edges and the same degree everywhere. The two-dimensional version — which colours pairs of points rather than points — separates them at once.

The natural response is to keep going. If two dimensions fix one dimension’s failure, three should fix two’s, and somewhere up the sequence is a version that works.

The two-dimensional version fails here, and the pattern continues: for every $k$ there are two graphs the $k$-dimensional refinement cannot separate. That is the Cai–Fürer–Immerman theorem of 1992, and its construction is one small gadget repeated.

What each dimension can see #

The hierarchy is worth stating precisely because the pattern in it is the whole story.

One dimension colours points by their degree, then by the multiset of their neighbours’ colours, and repeats. It computes every quantity expressible as how many neighbours have this property.

Two dimensions colours pairs, and refines a pair’s colour by the multiset over all third points of the pair of colours formed. It computes, among much else, how many common neighbours a pair has — which is what separates the six-cycle from two triangles, since an adjacent pair in a triangle has one common neighbour and in a hexagon has none. That is the locality argument counted rather than bounded: what a fixed number of pebbles sees is a fixed neighbourhood, and here the neighbourhood is measured instead of merely bounded.

$k$ dimensions colours $k$-tuples, and is exactly as strong as the $(k+1)$-pebble game — which is exactly as strong as the fragment of first-order logic with counting that uses $k+1$ variable names. Three descriptions of one hierarchy, which is what makes it worth understanding rather than merely a family of algorithms.

And each level is strictly stronger than the last. The hero figure’s pair is the smallest witness for $k = 2$. The general witness is the subject of the rest of this essay.

The pair in the hero figure #

Both graphs are strongly regular with parameters $(16, 6, 2, 2)$: sixteen points, six neighbours each, two common neighbours for every adjacent pair and two for every non-adjacent one. The first is the rows-and-columns graph of a $4 \times 4$ grid; the second is Shrikhande’s, a Cayley graph on $\mathbb{Z}_4 \times \mathbb{Z}_4$.

Two strongly regular graphs with the same parameters agree on everything two dimensions compute, and the reason is short: the two-dimensional refinement’s initial colouring distinguishes only adjacent, non-adjacent and equal, and its refinement step counts, for a pair, how many third points stand in each pair of relations to the two — which is exactly what the parameters fix.

What separates the two graphs is a property of three points at once: take a point and ask what shape its six neighbours form among themselves. In the grid graph they fall into two triangles — the three cells sharing a row, and the three sharing a column. In Shrikhande’s they form a single six-cycle. The figures compute that shape at every one of the sixteen points in each graph and find it constant and different.

A third pebble sees it. Place one pebble on the point, and two more can walk its neighbours and ask whether they join up; two pebbles cannot, because with only two names a point can be described relative to the one other pebble and nothing else.

That is worth stating as a sentence rather than as a game position, since it is the general principle the whole hierarchy runs on. With $k$ names available, a sentence can only ever describe a point by its relations to the $k-1$ others currently named — the names are reusable, so the sentence can be arbitrarily long, and the width of what it can hold in view at once is fixed. The two graphs above differ in a fact about three points, and a sentence with two names never has three points in view.

The gadget #

Strongly regular graphs are a supply of witnesses at $k = 2$ and they run out. The general construction produces a pair for every $k$ from one piece.

That parity is the entire construction. Replace every point of a base graph by its gadget, glue the edge-pairs, and the result has a large symmetry group — but the symmetries it has are constrained: at each gadget an even number of edge-pairs may be swapped, never an odd number.

Now build two graphs. One with every edge glued straight, and one with a single edge twisted — its two points exchanged before gluing.

They are not isomorphic. An isomorphism would have to undo the twist, which means swapping an odd number of pairs somewhere, and the parity forbids it — an argument that is a global count of local parities, exactly as a shuffle’s sign is.

And the $k$-dimensional refinement cannot see the twist, provided the base graph is chosen with enough connectivity. That is the theorem’s hard half: $k$ tuples of points see only a bounded part of the graph at a time, the twist can be moved around by local symmetries, and if the base graph’s treewidth exceeds $k$ then no set of $k$ pebbles can pin it down.

The figure enumerates every one of the eight sign patterns and every one of the twenty-four relabellings of the four middle points, and reports which patterns are realised. Four, all even.

Why the base graph has to be wide #

The construction’s one hypothesis is about the base graph, and it is worth saying what it is because it is where the $k$ enters.

Replacing every point of a base graph $G$ by a gadget gives a CFI pair, and the $k$-dimensional refinement fails to separate them provided $G$ has treewidth above $k$. Treewidth measures how far a graph is from being a tree: a tree has treewidth one, a cycle two, a $k \times k$ grid about $k$.

The reason is a pebble-game argument. With $k+1$ pebbles, the spoiler is trying to pin down where the twist is; the duplicating player moves it away using the gadgets’ local symmetries; and whether that can always be done is a question about whether $k+1$ pebbles can separate the base graph — which is exactly what treewidth measures, in the cops-and-robber characterisation where $k+1$ cops catch a robber precisely when the treewidth is at most $k$.

So the theorem’s three quantities are one quantity. The number of pebbles, the number of variables, and the treewidth the base must exceed are the same $k$, and the construction needs a base graph of unbounded treewidth — a grid will do — to produce witnesses at every level.

That also says how big the witnesses are. A base of treewidth $k$ needs about $k^2$ points, each becoming a gadget of size exponential in its degree — bounded, since the base can be taken of degree three — so the CFI pair on $n$ points defeats refinement at dimension about $\sqrt{n}$. Sharpening the base graph’s family improves that to linear, which is the form the theorem is usually quoted in.

What the theorem rules out #

The result’s importance is about an algorithm rather than about logic, and the negative it delivers is sharp.

Graph isomorphism has no known polynomial algorithm, and the most natural candidate strategy is: run $k$-dimensional refinement for a large enough fixed $k$, and if the colourings agree, declare the graphs isomorphic. That is a polynomial algorithm for each fixed $k$ — the cost is about $n^{k+1}$ — so a $k$ that worked for all graphs would settle the problem.

Cai, Fürer and Immerman showed no fixed $k$ works, and more than that: their construction gives, on $n$ points, a pair that $\Omega(n)$-dimensional refinement cannot separate. So the required $k$ grows linearly with the size of the graph, and $n^{k+1}$ with $k$ linear in $n$ is exponential.

The strategy is dead, and it is dead for a structural reason rather than because nobody has tuned it. That is the useful kind of negative result: it says which direction not to go.

Where the witnesses come from below #

The hierarchy’s first two levels have named witnesses and it is worth collecting them, because how quickly they run out is the argument for needing a construction.

Level one. Any two regular graphs of the same degree and size — a six-cycle and two triangles is the smallest. There are enormously many, and finding them is no work at all.

Level two. Two strongly regular graphs with the same parameters. There are $(16,6,2,2)$ pairs, $(25,12,5,6)$ pairs, $(26,10,3,4)$ pairs and so on, and the supply is real but thin — strongly regular graphs are hard to construct and most parameter sets admit at most one.

Level three. Here the named families stop. Objects agreeing on every three-point count are called coherent configurations of a certain kind, and pairs of them that are non-isomorphic exist and are not easy to write down.

So the hierarchy’s witnesses are found by hand at one and two and by construction thereafter, and the construction is what the gadget supplies. That is the practical reason the CFI paper mattered: not that anybody doubted the hierarchy was strict, but that nobody could produce witnesses past the second level until it appeared.

It is also worth noticing that the hero figure’s pair is exactly what anybody would find at level two by looking, and the gadget’s pair at level two is much larger. A construction that works at every level is nearly always worse than the best hand-made witness at any particular level, which is the usual trade between generality and size.

What the theorem does not rule out #

Two things, and both matter for what happened next.

It does not rule out a polynomial algorithm. Babai’s 2015 result gives a quasi-polynomial one — running time $n^{O((\log n)^c)}$ — and it uses group theory rather than refinement. The refinement hierarchy is one approach among several, and closing it off said nothing about the others.

And it does not make refinement useless. The CFI graphs are constructed to defeat it and are not what anybody meets. One-dimensional refinement alone distinguishes almost every pair of random graphs, and the practical isomorphism tools — nauty and its relatives — use refinement as their core with backtracking on top of it. The hierarchy is strict and the first level is nearly always enough, which is the standing relationship between a worst case and a distribution — the same one the zero-one law describes from the other direction, where a random graph’s first-order properties are all decided and all decided the same way.

There is a third consequence and it is the one the logic side cares about. The counting fragment with $k$ variables is exactly $k$-dimensional refinement, so the theorem says no fixed number of variables, even with counting quantifiers, defines graph isomorphism. Which is a statement about expressibility with no algorithm in it, and it settles a question about fixed-point logic with counting that had been open since Immerman asked it.

The same shape, in a much older place #

The gadget’s mechanism — a construction whose local pieces are all alike and whose global object is decided by a parity — is old and has a well-known instance worth setting beside it.

An orientation. A surface built by gluing polygons is orientable or not according to whether the gluings’ signs multiply to plus — a global parity of local choices — and no local inspection decides it.

A covering. A branched covering exists or not according to whether a product of permutations comes out right, and the losses at the branch points must add to an even number for exactly the reason the gadget’s swaps must.

And a shuffle’s sign. The parity of a permutation is unchanged by any decomposition into transpositions, so it is a genuine invariant of an object presented in arbitrarily many ways — and it is literally the invariant the gadget is built from.

In all four the pattern is: a quantity that is local, a rule that composes it, and an invariant nothing local can see. The gadget is that pattern engineered on purpose, to be invisible to any instrument that looks at $k$ points at a time.

What three descriptions of one hierarchy buys #

The identification of $k$-dimensional refinement with the $(k+1)$-pebble game and with $(k+1)$-variable counting logic is stated above as a fact and is worth dwelling on, because it is what makes the theorem usable in three subjects at once.

An algorithm designer reads it as: this family of algorithms is exactly this strong, and no tuning changes that.

A logician reads it as: this fragment defines exactly these properties, and adding counting quantifiers to a fixed number of variables buys exactly refinement.

A combinatorialist reads it as: these two graphs agree on every count of a certain locality, which is a statement about invariants with no algorithm and no logic in it.

One theorem, proved once, in three subjects that developed separately. That is the recurring reward of the game all of this is about: a question about all sentences becomes a question about one search, and a question about one search becomes a question about counting.

And it is why the negative result lands so hard. A counterexample to one of the three descriptions is a counterexample to all of them — so the CFI construction simultaneously kills an algorithmic strategy, settles a question about fixed-point logic with counting, and produces a family of graphs no local invariant distinguishes.

The pair itself is never drawn #

The CFI graphs are never drawn. The gadget is one vertex’s worth; a full pair over a base graph of treewidth four has hundreds of points and is unreadable at any size. What the figure establishes is the gadget’s parity property, exhaustively; that repeating it defeats $k$-dimensional refinement is the theorem, and it is prose.

The two-dimensional refinement is run and its failure is a single comparison. The figure computes both graphs’ stable two-dimensional colourings and finds them equal. That they are equal because the parameters agree is the argument, and no figure shows a refinement step.

And the separating property is checked and not proved to need three pebbles. The neighbour shapes differ, at every point of both graphs, and the claim that no two-pebble strategy detects that is the theorem’s content rather than the figure’s.

Still open: the boundary at two variables #

This result is about how many variables are needed to separate structures, and the answer is that no fixed number suffices. A different question can be asked of the same resource: how many variables a sentence may use before its satisfiability stops being decidable.

The answer is sharp and small. Two variables give a finite model property — every satisfiable sentence has a model of bounded size — so satisfiability can be decided by searching a bounded space. Three variables do not, and satisfiability there is undecidable. The whole boundary falls between two and three.

A hierarchy that does not collapse #

The habit is about what to conclude when a method fails and a refinement of it succeeds.

Colour refinement fails; two dimensions succeed. The inference so enough dimensions succeed is natural, and it is wrong here in the strongest available way — not merely unproved, but refuted by a construction that defeats every level at once.

What makes the refutation possible is that the construction is uniform. A separate counterexample at each level would show the hierarchy does not collapse at any particular point and leave open that it collapses somewhere. One gadget, repeated, gives a single mechanism that scales with $k$ — and a mechanism that scales is what turns a sequence of counterexamples into a theorem.

So the question to ask of a hierarchy of methods is not whether each level beats the last. It is whether there is a single construction that grows with the level, because that is what settles the whole hierarchy in one argument.