Three is where it can hear

The set has to be even outward found the rule behind an invariant’s hearing. Godsil–McKay switching takes a graph and a switching set $D$ of four vertices and produces another graph with the same spectrum, usually a different one. The critical group — the torsion of the cokernel of the reduced Laplacian, computed exactly by the Smith normal form — sometimes tells the two apart and sometimes does not, and the group hears a switch only at two had found that when it does, it is always at the prime two. The rule was exact: the switch is heard if and only if every vertex of $D$ has an even number of neighbours outside it, which is to say that the indicator vector of $D$ is a null vector of the Laplacian modulo two. Every switch at three degrees obeyed it.

The reason two is the prime is that four-vertex switching conjugates the adjacency matrix by an orthogonal matrix with entries in $\tfrac12\mathbb{Z}$, and only at two can such a conjugation fail to be an equivalence over the integers. The essay’s closing section followed the arithmetic one size up. “Godsil–McKay switching on six vertices conjugates by a matrix of thirds. The prediction is that the critical groups of six-vertex switches differ only at the prime three, and only when $L\mathbf{1}_D$ vanishes modulo three — each vertex of the set with an outward degree divisible by three — so that on cubic graphs the six-vertex switches with nothing inside are heard and those with any edge inside are not.”

The first two clauses hold. The third has no graphs to apply to, and the rule that replaces the second is the more interesting part.

Six vertices, and the switches they make #

A six-vertex switching set is a set $D$ that induces a regular graph, such that every vertex outside it is adjacent to none of $D$, to three of it, or to all six. The switch complements the edges between $D$ and each outside vertex adjacent to exactly three, giving every such vertex the other three instead; the result is cospectral with the original. For random regular graphs the conditions are restrictive, so the search is exhaustive: every six-subset of every graph drawn, 1,500 graphs in each of five cases — quartic graphs of 12, 13 and 14 vertices and quintic graphs of 12 and 14 — keeping the switches whose result is connected and not isomorphic to the original. That leaves 621 switches. Both critical groups of every pair are computed exactly.

The census has a shape before any group is computed. On quartic graphs every switch found has induced degree one, so outward degree three — 74 at twelve vertices, 7 at thirteen and none at fourteen. On quintic graphs of twelve vertices every switch has induced degree two, outward three; at fourteen, 62 have induced degree one, outward four, and 2 have induced degree two. Of the 621, 559 have an outward degree divisible by three and 62 do not.

At three alone #

Every switch the critical group hears — 197 of them — differs from its partner in the 3-primary part of the group and in no other, and the two groups have the same order on every pair, as they must: a switch preserves the Laplacian’s spectrum on regular graphs, and the group’s order is the number of spanning trees, the product of the non-zero Laplacian eigenvalues over the number of vertices. What moves is how the same power of three is split into cyclic factors.

The commonest pair, on 130 switches, is $\mathbb{Z}_3 \times \mathbb{Z}_3$ against $\mathbb{Z}_9$: order nine both, split into two factors on one side and one on the other. Next come $\mathbb{Z}_{27}$ against $\mathbb{Z}_3 \times \mathbb{Z}_9$, 29 times, and $\mathbb{Z}_{27}$ against $\mathbb{Z}_3^3$, 10 times. Every one is the four-vertex picture with two replaced by three: a finer invariant that hears less found the 2-parts rearranged in exactly this way. And no switch with outward degree four is heard — none of the 62 on quintic graphs of fourteen vertices. So the first two clauses of the prediction hold on every switch measured: heard only at three, and only when the outward degree is divisible by three.

Divisible, and still silent #

The four-vertex rule was an if and only if. The six-vertex one is not.

On quartic graphs of twelve vertices 40 of the 74 divisible switches are heard, 54 per cent; of thirteen, 3 of 7; on quintic graphs of twelve, 154 of 476, 32 per cent; of fourteen, neither of the 2. The condition $L\mathbf{1}_D \equiv 0 \pmod 3$ holds on all of them — on the vertices of $D$ because the outward degree is three, and on every outside vertex because it is adjacent to three or six of $D$ — and it does not decide anything. For four vertices the null vector was the whole story; for six it is only the door.

What does decide it, nearly, is the rank of the Laplacian modulo three.

On quintic graphs of twelve vertices, 152 of the 154 heard switches change the rank of the Laplacian modulo three, and none of the 322 silent ones does. Across all five cases the rank moves on every heard switch but those two and on no silent switch at all. The two it misses are the pairs $\mathbb{Z}_3 \times \mathbb{Z}_3 \times \mathbb{Z}_{27}$ against $\mathbb{Z}_3 \times \mathbb{Z}_9 \times \mathbb{Z}_9$, where the number of factors divisible by three is the same on both sides and only their sizes differ: the rank modulo three counts the factors divisible by three, so it is blind exactly to a rearrangement that keeps that count. Everything else is a change of count, and an elimination over a field of three elements sees it.

That turns the four-vertex result inside out in a useful way. There, a condition on the switching set alone — its outward parity — decided audibility. Here, the set’s condition is necessary and the decision is made by the whole graph’s rank over the field the switch’s denominators live in. Read in the other direction, the earlier rule now looks like a special case: at two, whenever the set’s indicator was a null vector, the rank modulo two moved. The four-vertex essays found that by a different route — the group hears a switch only at two counted a rank modulo two finding 158 of 181 separated pairs — and this measurement says that at three the rank is the rule and the set’s condition the filter in front of it.

A rule from the set does not do it #

If the rank decides, the obvious hope is a condition on the original graph and the set that predicts the rank’s move before the switch is made, as the four-vertex rule did. The natural candidate is the column space: since $L\mathbf{1}_D \equiv 0$, the indicator is in the kernel modulo three, and a symmetric matrix’s kernel and column space are orthogonal complements over a field, so $\mathbf{1}_D$ either is or is not also in the column space, depending on whether it is orthogonal to every other kernel vector. That is a property of the original graph alone, computed by one more rank.

It decides nothing. On quartic graphs of twelve vertices the 40 heard switches split 22 with the indicator in the column space and 18 without; the 34 silent ones split 23 and 11. On quintic graphs of twelve, the heard split 99 and 55 and the silent 177 and 145. Every combination occurs in quantity. The rank of the switched graph’s Laplacian moves or does not, and nothing about where $\mathbf{1}_D$ sits in the original’s spaces modulo three foretells which. Whatever the rule is, it involves the switch’s effect on the other vertices — the outside vertices adjacent to three of $D$ whose edges are complemented — and not the set’s indicator alone.

What a determinant does not determine is the account of why two integer matrices with the same determinant can differ in their invariant factors, which is all a heard switch is: the same number of spanning trees, distributed differently among cyclic factors. The six-vertex switches make that concrete at the prime three, and a graph is alternating modulo two is a reminder that which prime a question is asked at can change the law it follows entirely.

The critical group’s partial hearing is put in proportion by an invariant that hears everything. The effective resistances between every pair of vertices — read off the pseudoinverse of the Laplacian, real numbers rather than a group — differ between the two graphs of every six-vertex pair measured: 74 of 74 on quartic graphs of twelve vertices, 476 of 476 on quintic graphs of twelve, 64 of 64 on quintic graphs of fourteen, sorted and compared to $10^{-9}$. That matches the four-vertex result, where the resistances also separated every pair the group missed. The group is the coarser instrument by design: it keeps only the integer structure of the Laplacian’s cokernel and discards everything a resistance, a ratio of minors, would carry. It hears the switch when the switch rearranges that integer structure, which is a question about one prime, and the resistances hear it whenever anything moves at all.

A distance computed by a solve introduced the resistances as the one graph quantity with no combinatorial route to it; as a test of graph identity it is the sharper of the two and the dearer, a dense solve against a Smith form over the integers, and on these graphs the cheaper test is wrong two thirds of the time.

The cubic switches are not there #

The prediction’s last clause was about cubic graphs: switches with nothing inside the set heard, those with any edge inside not. It assumed there were cubic graphs with six-vertex switches to test. There are almost none, and counting edges says why.

On a cubic graph, a vertex outside $D$ adjacent to three of $D$ uses all three of its edges on $D$, and none can be adjacent to six. If $D$ has $d$ edges inside each vertex, its six vertices send $6(3 - d)$ edges outward, and every one of them ends at an outside vertex that sends all of its edges back. So $D$ and the $2(3 - d)$ outside vertices it touches have no edge leaving them: they are a connected component, and in a connected graph they are the whole graph. The order is $6 + 2(3 - d)$: twelve when nothing is inside, ten when each vertex of $D$ has one neighbour in it, eight when two.

The measurement agrees with the arithmetic and goes one step further. At eight vertices 2,769 of 4,000 random cubic graphs have a six-vertex switching set, at ten 1,450 and at twelve 47; at fourteen and sixteen, none in 400 each. And every one of the 9,985 switches found — 7,818, 2,073 and 94 — returns a graph isomorphic to the one it started from. At twelve vertices with nothing inside, the graph is bipartite with $D$ as one side, and the switch replaces it with its bipartite complement in $K_{6,6}$, which for these graphs is the same graph relabelled. The prediction’s cubic switches with nothing inside exist, and they are switches that change nothing, so there is nothing for the critical group to hear.

How far the group moves #

The nine kinds of rearrangement in the figure differ in how far they move the count of factors divisible by three, the 3-rank. On 177 of the 197 heard switches it moves by one — two factors become one, as $\mathbb{Z}_3 \times \mathbb{Z}_3$ becomes $\mathbb{Z}_9$, or one becomes two. On 18 it moves by two: $\mathbb{Z}_{27}$ against $\mathbb{Z}_3^3$ ten times and $\mathbb{Z}_3 \times \mathbb{Z}_3 \times \mathbb{Z}_9$ against $\mathbb{Z}_{81}$ eight times, a three-factor group collapsing into a single cyclic one. And on the two the rank misses it does not move at all. A six-vertex switch changes the rank of the Laplacian modulo three by at most two on everything measured, as a change confined to the edges between six vertices and their neighbours might be expected to; that bound is observed, not proved, and a switch on more vertices would be the place to look for a larger move. The two rank-blind switches are the only ones whose rearrangement keeps three factors on both sides and trades a 27 for a pair of nines.

What the thirds changed #

The prediction carried over the four-vertex essay’s mechanism exactly, and two of its three clauses came through: the prime and the necessary condition are both set by the switch’s denominator, as the earlier argument said they would be. What did not come through is the sufficiency. One reading of why, offered as a reading: a matrix of halves has only one way to fail to be invertible over the integers modulo two, so the null-vector condition is the whole of its failure; a matrix of thirds acts on the 3-primary part through a larger group of possibilities, and whether a given switch rearranges the group depends on how the set’s indicator sits relative to the rest of the Laplacian’s kernel modulo three, which the set alone does not know.

The census also says something about how rare six-vertex switching is. The spectrum is not the graph and the essays after it found four-vertex switches by the hundred on a few thousand graphs; six-vertex switches on graphs of fourteen vertices are a few dozen in 1,500, and on cubic graphs past twelve they do not exist. Each spectrum hears the other’s pairs compared the invariants that separate four-vertex cospectral pairs; for six-vertex pairs the same comparison would need far more graphs to have anything to compare.

What 621 switches do not show #

The graphs are random regular graphs of 12 to 14 vertices and degree 4 or 5, every switching set of each tried; larger orders give more sets per graph but far fewer graphs a session can search, and the shares heard — 54 and 32 per cent — are each from one case’s few hundred switches. The two switches the rank misses are both on quintic graphs of twelve vertices, and whether the rearrangements that keep the count of 3-divisible factors are rare in general or only here is not known. The thirteen-vertex quartic case contributes only seven switches and the fourteen-vertex quartic case none, so the quartic result is essentially one order’s; none of the 1,500 quartic graphs of fourteen vertices drawn here yielded a six-vertex switch that gave a new graph, and why such switches thin out so fast with the order is a question about random regular graphs rather than about the group. The cubic result rests on the edge-counting argument and on random samples; the samples found every switch isomorphic, and that bipartite complements of twelve-vertex cubic bipartite graphs are always isomorphic to the original is checked on the 47 graphs found, not proved.

Still open: a rule for the rank, and switches on more vertices #

What moves the rank. The set’s indicator does not foretell the rank’s move. The prediction with a sign is that the outside vertices do: that a switch is heard exactly when the three-dimensional space spanned modulo three by the indicators of the outside vertices’ complemented neighbourhoods — the parts of $D$ each outside vertex gains — is not contained in the original Laplacian’s column space modulo three, and that this test, computed before switching, reproduces every heard and silent switch here except the two rank-blind ones.

Eight vertices. Godsil–McKay switching on eight vertices conjugates by a matrix of quarters, whose denominators are again a power of two. The prediction is that eight-vertex switches on random quintic graphs are heard only at two, never at three, and that on cubic graphs, by the same counting as here, they exist only up to order sixteen and change nothing.