The set has to be even outward

The group hears a switch only at two made cospectral regular graphs by Godsil–McKay switching: take four vertices $D$ that induce a regular subgraph, with every other vertex adjacent to none, two or all four of them, and for each vertex adjacent to exactly two, swap which two. The result has the same adjacency spectrum, and on a regular graph that brings the Laplacian spectrum, the tree count and the degree sequence with it; the critical group — the Smith form of a reduced Laplacian — is the only exact invariant left to tell the two apart. On 705 distinct pairs of 3- and 4-regular graphs it separated 181 quartic pairs and no cubic one, and on every pair the two groups agreed at every odd prime: a switch is conjugation by a matrix with halves in it, and the group hears it only through its 2-part.

Its last section asked why the cubic pairs were silent, and offered a mechanism with a prediction attached. “On a cubic graph no outside vertex can be adjacent to all four of a switching set, and every switched vertex is adjacent to exactly two. The prediction with a sign is that in both of these cases” — cubic sets, and quartic sets with a matching inside — “the switch is an equivalence of Laplacians over the integers themselves … so that the two critical groups are equal on every such pair at every order, and a cubic pair with a different group cannot be made by switching on four vertices at all.”

Every switch of those two kinds measured here is silent, at every order and degree reached, so the prediction’s conclusion stands. Its reason does not, and replacing the reason turns up a second rule that fits all 705 earlier pairs and fails on the first new family. The third rule holds everywhere it was tested, and it is a statement about parity.

The kinds of switch #

A switching set of four in a $k$-regular graph is described by three numbers. The degree $d$ of the subgraph it induces: nothing inside ($d = 0$), a perfect matching ($d = 1$), a four-cycle ($d = 2$). The number $f$ of outside vertices adjacent to all four. And the number $h$ adjacent to exactly two — the vertices the switch rewires. Counting the edges that leave the set gives $4(k - d) = 2h + 4f$, so $h = 2(k - d - f)$; any two of the numbers fix the third.

The earlier census met three kinds. All 118 cubic pairs had $d = 0$ and $f = 0$, hence $h = 6$. The 587 quartic pairs split into 346 with $d = 0, f = 0$ and $h = 8$; 231 with a matching inside, $d = 1$, $f = 0$, $h = 6$; and ten with $d = 0$, $f = 1$, $h = 6$. The new measurement adds quintic graphs: 160 random 5-regular graphs on each of twelve and fourteen vertices, every switching set of each tried, and kept whenever the switched graph is not isomorphic to the original — 98 switches of six kinds.

Not the vertex adjacent to all four #

The earlier essay’s mechanism was local: a cubic graph cannot have an outside vertex adjacent to all four, so every outside vertex the switch touches is adjacent to exactly two. But the quartic pairs with $d = 0$ and $f = 0$ are in exactly that situation — no full vertex, every touched vertex adjacent to two — and they are the pairs the critical group hears: 181 of 346, more than half. Whatever makes the cubic pairs silent, it is not the absence of a full vertex.

And the quartic pairs that do have a full vertex are silent: none of ten. If anything, the full vertex goes with silence rather than sound.

A rule that fits the census and fails at degree five #

The census suggests a count. Among the cubic and quartic pairs, every heard switch has $h = 8$ half-adjacent vertices and every silent one has $h = 6$ — the cubic pairs, the quartic sets with a matching, the quartic sets with a full vertex. A rule “heard only when $h$ is a multiple of four” fits all 705 pairs without exception, and it is the kind of rule a switch could plausibly obey: the switch moves $h$ edges’ worth of adjacency in pairs, and a count modulo four is what an argument about halves might produce.

The quintic graphs break it. A quintic switching set with a matching inside and one full outside vertex has $h = 2(5 - 1 - 1) = 6$, and its critical groups differ on seven of eleven switches. A rule that says silent is useful only if the switches it calls silent are silent, and this one fails on the first family it was not fitted to.

Even outward #

What separates every heard kind from every silent one at all three degrees is $k - d$, the number of neighbours each vertex of the set has outside it. Heard kinds have four: quartic sets with nothing inside, quintic sets with a matching inside, with or without a full vertex. Silent kinds have three or five: every cubic set, quartic sets with a matching, quintic sets with nothing inside or a four-cycle. Not one switch with an odd outward degree is heard among the 363 measured.

The dial shows the rule degree by degree. At three, the only kind met has three outside neighbours each, and nothing is heard. At four, the independent sets have four and are heard on 52 per cent; the sets with a matching have three and are silent. At five, the sets with a matching have four and are heard on 42 per cent, the independent sets and four-cycles have five and three and are silent.

The rule has a clean algebraic statement. Multiply the Laplacian by the indicator vector of the set, $\mathbf{1}_D$. On a vertex of $D$ the result is its degree less its neighbours inside $D$, which is $k - d$. On a vertex adjacent to exactly two of $D$ it is $-2$, on a full vertex $-4$, and on every other vertex zero.

Every entry off the set is even by construction — that is what the switching condition requires — so the vector is zero modulo two exactly when $k - d$ is even. The rule, stated without counting anything, is that the critical group can hear a switch only when $\mathbf{1}_D$ is a null vector of the Laplacian over $\mathbb{F}_2$. The earlier essay located the effect at the prime two because the switching matrix has halves in it; this says which switches the halves can reach. A switch is the reflection $x \mapsto x - \tfrac12(\mathbf{1}_D^{\mathsf T}x)\,\mathbf{1}_D$ restricted to the set, and the place a halving can touch the cokernel of the Laplacian is through the image of $\mathbf{1}_D$ — which, modulo two, is zero or it is not.

There is a reason to expect the null space modulo two to be the right place to look, and it is the same fact the rank depends on the ring built on. The number of invariant factors of the Laplacian that are even is the dimension of its null space over $\mathbb{F}_2$ — rank modulo a prime counts the invariant factors the prime does not divide, which each column divides by the prime used from the other side — so the 2-part of the critical group has exactly as many cyclic factors as $L$ has independent null vectors modulo two, less the one every Laplacian has in the all-ones vector. A switch that changes the 2-part has to change something that space counts or carries. A set whose indicator is not in that space is, modulo two, invisible to it; a set whose indicator is in it is one of the vectors the 2-part is made of.

The statement is measured, not proved: a proof would have to show that when $L\mathbf{1}_D$ is odd somewhere the two reduced Laplacians are related by integer unimodular matrices, which is the earlier essay’s prediction made precise, and that construction is not written here.

Necessary, not sufficient #

A null set allows the group to hear the switch; it does not make it. Of the null kinds, quartic independent sets are heard on 52 per cent, quintic sets with a matching on 42 per cent and on seven of eleven with a full vertex. The fourth null kind, a quartic set with one full vertex, is heard on none of its ten. In a quartic graph that full vertex has all four of its neighbours in $D$, so the set and the vertex form a closed piece of the graph that the switch rewires only at its boundary; whether that is why, ten pairs cannot say.

The earlier essay’s other condition was room: the group can only differ at two if it has a 2-part, and it found no pair separated whose tree count had fewer than three factors of two. The figure tests that against the null rule, and the two come apart. Every null switch measured has at least two factors of two in its tree count, which the rule makes likely — a null vector modulo two is an even invariant factor waiting to happen — and the share heard does not climb with more: 75 per cent of 32 switches at exactly two factors, 51 per cent at three, 33 at four, 48 at five, 57 at six or more. The 32 at two factors are all quintic, so the earlier essay’s threshold of three, drawn from cubic and quartic pairs, was itself a property of those degrees. Among non-null switches the share is zero at every power, including the cubic and quartic pairs whose tree counts carry six or more. A non-null set is silent even when the group has all the room it could want, and a null set is heard about half the time whatever the room.

A test that costs one vector #

The practical side of the rule is that it is cheap and comes first. The critical group of a graph on twenty vertices is the Smith form of a nineteen-by-nineteen integer matrix, computed here in exact arithmetic because its entries grow — the cost the swell was one-sided measured, cheap for these sizes by plain two-sided elimination but still cubic in the order with integers that widen as it goes; the parity of $L\mathbf{1}_D$ is four additions per vertex of the set. A search for cospectral regular graphs with different critical groups — the search the earlier essay ran, which drew three thousand graphs at each order and kept the pairs — can discard every switching set with an odd outward degree before switching, and on the census that is 349 of 705 pairs that could never have separated. On the quintic sample it is fourteen of 98 switches; on cubic graphs, everything but the matching sets, which the next section shows to be empty of new graphs anyway.

The same parity reading applies to the Laplacian’s relatives. On a regular graph the combinatorial and normalised Laplacians are scalar multiples of each other, as two Laplacians of one graph measured, and the adjacency matrix differs from the Laplacian by a multiple of the identity. Modulo two, $k$ times the identity is the identity or zero according to the parity of $k$, so the adjacency matrix’s null space modulo two and the Laplacian’s coincide when $k$ is even and differ when $k$ is odd. The rule could have been stated for $A\mathbf{1}_D$ instead, with the parity of $d$ in place of $k - d$, and on odd degrees it reads the other way: that is the same fact seen through a matrix that differs by an odd scalar.

What the cubic graphs could and could not do #

The prediction’s strongest clause was that a cubic pair with a different group “cannot be made by switching on four vertices at all”. The rule says what that would require: a cubic switching set with an even outward degree, which means two outside neighbours each, which means a matching inside the set. Such sets exist on cubic graphs, and often: 52 of them in 300 random cubic graphs on sixteen and twenty vertices. Every one of the 52 switches to a graph isomorphic to the original. On a cubic graph the only switch the critical group could hear produces no new graph, and the clause holds — for a reason the prediction did not give, and on the evidence of a sample rather than an argument.

A finer invariant that hears less found the critical group finer than the tree count and still blind to most cospectral pairs; each spectrum hears the other’s pairs found the adjacency and Laplacian spectra complementary everywhere except on regular graphs. This adds a structural reason to the list of what the group cannot hear, one that can be checked before the Smith form is computed: form $L\mathbf{1}_D$ and look at its parity. The spectrum is not the graph began the subject with a cospectral pair and the question of what else distinguishes them; on regular graphs switched on four vertices, the answer for the critical group is now a parity test on one vector.

The two failures before the rule are worth keeping in view, because both were reasonable and both fitted their data. The full-vertex mechanism explained the cubic silence and was refuted by the quartic graphs already in the census, which no one had looked at in that light. The half-count rule fitted all 705 pairs exactly and was refuted by the first degree it was not fitted on. The null rule has now survived one such extension, from two degrees to three, and the honest status of it is the same as the half-count rule’s before the quintic graphs: a rule that fits everything measured, with a prediction attached that a sextic graph or a six-vertex switch could break. What it has that the half-count rule lacked is a reason that can be stated without the data: a vector the 2-part is built from, and a switch that touches it or does not.

What a few hundred switches do not settle #

The quintic sample is 98 switches, and three of its six kinds have six or fewer examples; the rule’s silence on them is consistent with it, not evidence for it. The quartic full-vertex kind, heard on none of ten, is the one place the null rule allows a sound and none was heard, and ten is too few to say whether it is silent by structure. Switching sets of six and more vertices, which conjugate by matrices of thirds and other fractions, are outside everything measured; the analogue of the rule would be a null vector modulo the switching matrix’s denominator, and that is a prediction rather than a finding. And the claim is about the critical group only: resistances, which the earlier essay found separate every pair, are not touched by any parity.

Still open: the unimodular construction, and sets of six #

The construction behind the silence. If $L\mathbf{1}_D$ is odd somewhere, there should be integer unimodular matrices $U$, $V$ with $L' = U L V$ built from the switch itself. The prediction with a sign is that $U = V^{\mathsf T}$ can be taken as the switch on the index-two sublattice of vectors whose entries on $D$ sum to an even number, extended by one integer vector chosen where $L\mathbf{1}_D$ is odd — and that this construction fails, as it must, on every null set the group hears.

A switch on six. 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.