The group hears a switch only at two

Each spectrum hears the other’s pairs measured which invariants tell cospectral graphs apart in every graph on up to eight vertices. On pairs that share a Laplacian spectrum the adjacency spectrum separated all of them; on pairs that share an adjacency spectrum the Laplacian spectrum did, and so did the spanning-tree count, which the Laplacian spectrum fixes and the adjacency spectrum does not. The critical group — the abelian group whose order is the tree count, read off the Smith normal form of a reduced Laplacian — separated exactly the pairs the tree count did, because on those pairs its order already differed.

Its last section named the case where all of that collapses. “For a k-regular graph $L = kI - A$, so the two spectra carry one piece of information and the complementarity above collapses. Regular cospectral pairs exist at sizes beyond this census. On them the tree count is shared, the degree sequence is shared, and the critical group is the only exact invariant here left to speak; how often it does is the question the earlier essay first asked and this census cannot reach.”

It speaks on three quartic pairs in ten and on no cubic pair. And when it speaks, it says the same thing every time, in the same place: the prime two.

Making regular pairs instead of finding them #

The census cannot reach regular cospectral pairs because there are few regular graphs on eight vertices and fewer cospectral pairs among them. They can be made instead. Godsil and McKay’s switching takes a graph with a set D of vertices that induces a regular subgraph, such that every vertex outside D is adjacent to none, half or all of D, and for every outside vertex adjacent to exactly half of D, swaps its edges into D for its non-edges. The result has the same adjacency spectrum. A graph cospectral with a k-regular graph is k-regular — the largest eigenvalue and the sum of the squared eigenvalues together force it — so the switched graph’s Laplacian $kI - A$ has the same spectrum too, and with it the tree count, the degree sequence and the number of triangles.

The Laplacian here is the combinatorial one, $D - A$; for a regular graph it differs from the normalised one of two Laplacians of one graph only by a factor of the degree, so on these pairs every Laplacian in this collection shares one spectrum. The measurement uses sets of four vertices. For each of seven combinations of order and degree — 3-regular graphs on 14, 16, 18 and 20 vertices, and 4-regular graphs on 12, 14 and 16 — three thousand random connected regular graphs are drawn by the pairing model. Each is searched for a switching set; switched; tested for isomorphism with the original, since a switch often returns the same graph; and kept only if the pair is new, up to isomorphism of the unordered pair, because at small orders a random draw meets the same few pairs again and again. Each kept pair is checked to be cospectral and regular and to share a tree count, and its two critical groups are computed as the Smith normal form of the reduced Laplacian, in exact integers.

The tree count every pair shares comes from the matrix-tree theorem — the product of the nonzero Laplacian eigenvalues over the number of vertices, which a matrix with no numbers in it introduced as the one exact null vector in the field — and the critical group is the finer object whose order it is. Seven hundred and five distinct pairs survive: 118 cubic and 587 quartic. Most switches return an isomorphic graph — on cubic graphs, nearly all of them: of 1,997 cubic graphs that had a switching set, 1,852 switched back into themselves.

A switch that returns the graph it started from has found a symmetry rather than a new graph: the switched graph is the original under some relabelling of its vertices, so the trade of edges at D was one the graph’s own structure could absorb. The isomorphism test finds that relabelling whenever it exists, and such pairs are discarded. On cubic graphs that is the rule rather than the exception, and the few cubic switches that do produce a new graph are the ones whose surroundings break every such relabelling. Symmetry of this kind is what a partition decided in the last digit found turning an eigenvector into a whole plane of them; here it turns a switch into an identity, and the pairs worth measuring are what is left once every symmetric switch is discarded. That is also why the cubic counts are small — 118 distinct pairs from twelve thousand draws — and why their zero deserves its caution.

A third of the quartic pairs, none of the cubic #

The figure at the top of the page is every pair, split three ways. Pairs whose two groups are both cyclic share a group necessarily — a cyclic group is fixed by its order, and the order is the shared tree count — so on those the group cannot speak. The rest are pairs it could separate, and the figure counts how many it does. On quartic graphs it separates 36 of 126 pairs at twelve vertices, 97 of 300 at fourteen and 48 of 161 at sixteen: 29, 32 and 30 per cent, and about half of the pairs whose groups are not both cyclic. On cubic graphs it separates none — not one of 118 pairs, thirty of which have a non-cyclic group and so had room to differ.

The census’s rate, for comparison, was 435 of 1,022 Laplacian-cospectral pairs at eight vertices, two in five. That rate included pairs that differ in every invariant except the Laplacian spectrum. On regular pairs every spectral invariant is shared, and the group’s rate falls to a quarter overall — and to zero on the graphs of lowest degree.

The structure of the switching set divides the quartic pairs further. A set of four must induce a regular subgraph; on these graphs it induced either no edges or a perfect matching. Where the set is independent, the group separates 181 of 356 quartic pairs, a little over half. Where the set induces a matching, it separates none of 231. The cubic sets were all independent, and separated none of 118.

The odd part never moves #

The figure of transitions below lists the separated pairs’ groups as their parts at the prime two — the Sylow 2-subgroup, the product of the powers of two in the invariant factors. That is the only place they differ. On every one of the 705 pairs, separated or not, the two groups’ odd parts are identical: the same invariant factors once every factor of two is removed.

The most common separation is three factors of two arranged two ways — $\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2$ against $\mathbb{Z}_8$ — on 74 pairs; then $\mathbb{Z}_{16}$ against $\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_4$ on 27, and a cyclic 2-part against a split one in most of the rest. The odd part, which in these pairs runs from the tens of thousands to the millions, never differs by a single factor.

There is a reason, and it is short. A switch on a set of four is a similarity of adjacency matrices, $A_H = Q^{\mathsf T} A_G Q$, by an orthogonal matrix Q that is the identity outside D and $\tfrac12 J - I$ on it — every entry of Q is an integer or a half. The same Q relates the Laplacians, since the switch keeps every degree. Q and its inverse $Q^{\mathsf T}$ both have entries in the integers with two inverted, so over that ring the two Laplacians are equivalent, and their Smith forms over that ring agree. A Smith form over the integers with two inverted is the integer Smith form with every power of two struck out. So the odd parts must agree, on every pair any such switch can make; and whatever the critical group hears of a switch, it hears through the prime two. The 705 pairs are the measurement that says the argument and the arithmetic agree.

The 2-part has to be large enough to rearrange #

If the only place two groups can differ is their 2-part, the 2-part must have room to be arranged two ways. A 2-part of order two is $\mathbb{Z}_2$ and nothing else; of order four, $\mathbb{Z}_4$ or $\mathbb{Z}_2 \times \mathbb{Z}_2$. The measurement shows the room being used only from order eight up. Quartic pairs whose tree count has one or two factors of two are never separated, 136 pairs in all, though order four leaves room for two groups; from three factors of two the share jumps to 43 per cent, and at every larger size it stays between 28 and 57 per cent. The count of factors of two is shared by both graphs, so it is a property of the pair visible before either group is computed: a pair with an odd tree count, or a tree count with fewer than three factors of two, is one the critical group cannot separate.

The cubic pairs are separated at no size of 2-part, including the thirty with a non-cyclic group and the twelve whose tree count has five or more factors of two. Something about switching on a cubic graph keeps even the 2-part fixed — and the matching sets on quartic graphs share it. That something is not in the argument above, which allows any change at two; it is a sharper constraint the measurement shows and does not explain.

A rank over two elements finds most of them #

If a switch can only show at two, the cheapest test that looks at two should find most of what the group finds — and it does. Reduced modulo two, the reduced Laplacian has a rank over the field of two elements, and that rank is the number of its invariant factors that are odd; the number divisible by two is what is left. Two groups with the same order but a different count of even factors — $\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2$ has three, $\mathbb{Z}_8$ one — therefore have reduced Laplacians of different rank over two elements.

Of the 181 separated pairs, 158 are told apart by the rank over two elements alone: one Gaussian elimination over bits, no big integers, no Smith form. Seventeen more need the Smith form modulo four, where the count of factors divisible by four differs though the count of even ones does not — $\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_{16}$ against $\mathbb{Z}_4 \times \mathbb{Z}_4 \times \mathbb{Z}_4$ is the commonest — and the last six need it modulo eight. None needs more. The exact integer Smith form computed here, with its six- and seven-digit invariant factors, carries for these pairs no information that three bits of arithmetic do not.

That turns the essay’s measurement into a procedure. For two regular graphs already known to be cospectral, the critical group is worth computing only at the prime two, and only to the depth of the tree count’s 2-part; a rank over two elements is the first and nearly always the last step. The vertex nobody solves for found three ways of removing a Laplacian’s kernel that agree to fourteen digits; the reduced Laplacian here is the grounded one, and over two elements the choice of grounded vertex does not move the rank, since the Smith form of any reduced Laplacian is the same.

What the earlier census could not see #

At eight vertices the census found the critical group separating pairs mostly where its order already differed, or where the order factored two ways. The regular pairs remove the first possibility entirely and reduce the second to one prime. A finer invariant that hears less put the group beside the Laplacian spectrum as a strictly finer invariant that nevertheless separates fewer pairs, because its information is in the arithmetic of one integer rather than in a list of real numbers. The switching makes that concrete: the arithmetic the group can use, on any pair a switch on four vertices can make, is the arithmetic of the powers of two in that integer.

What the group lacks is not exactness but the right kind of information, and a real-valued invariant shows the difference. The effective resistance between two vertices, which a distance computed by a solve introduced as the one quantity in this field defined by a linear system, is not spectral: it depends on the eigenvectors as well as the eigenvalues. Sorted, the 66 to 190 resistances of a graph differ between the two graphs of every one of the 705 pairs. Their sum, the Kirchhoff index, is spectral — the number of vertices times the sum of the reciprocal nonzero Laplacian eigenvalues — and agrees on every pair to within $5 \cdot 10^{-13}$. A list of real numbers read off a solve hears every switch; an exact integer invariant hears a quarter of them, and only at two.

That also says where to look for regular cospectral pairs the group must separate: none can be made this way. Every pair a four-vertex switch produces agrees at every odd prime, so a test that wants to separate switched pairs has to work modulo two — the critical group’s 2-part, or the Smith form of the adjacency matrix taken over the field of two elements — and anything that ignores two is blind to them by construction. The spectrum is not the graph opened this line with one pair on six vertices; the measurement here says which half of the remaining information a whole class of pairs leaves open.

What 705 pairs do not show #

Switching on sets of four, at three cubic and three quartic orders, on random regular graphs drawn by the pairing model, which samples regular graphs nearly but not exactly uniformly. Switching on larger sets, and the other constructions of cospectral graphs, are not measured: a switch on a set of six uses a matrix with entries in thirds, and the same argument then predicts agreement at every prime except three. Pairs were kept once per isomorphism class of the pair; a graph with several switching sets could give several distinct partners, and only the first non-isomorphic one was taken from each draw. The critical groups are exact; the isomorphism tests are a colour refinement followed by a complete backtracking search, so a pair kept as non-isomorphic is non-isomorphic. Degrees five and above, where switching sets of four are rarer still, are not reached.

Still open: why cubic switches keep the 2-part, and a switch on six #

The cubic constraint. No cubic pair and no quartic pair with a matching switching set is separated, though thirty cubic pairs had a non-cyclic group. 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 the switch is an equivalence of Laplacians over the integers themselves — a unimodular change of basis, not only one over the integers with two inverted — 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.

A switch on six. Godsil–McKay switching on a set of six vertices conjugates by a matrix of thirds. The prediction is that on pairs it makes, the critical groups agree at every prime except three, and that the share separated is smaller than on four-vertex switches, because a tree count’s 3-part is smaller than its 2-part on most regular graphs of these orders.