A finer invariant that hears less

The spectrum is not the graph found the smallest pair of connected graphs a Laplacian spectrum cannot tell apart — a triangle and a square sharing a vertex, against the complete bipartite graph $K_{2,3}$ with a pendant edge — and checked it as an equality of integer polynomials rather than of computed eigenvalues. It ended by listing what the two graphs share correctly: the number of edges, the number of components, the number of spanning trees, twelve each.

What a determinant does not determine then pointed at the one thing on that list with more structure than its size. The number of spanning trees is a determinant, and a determinant is the product of a matrix’s invariant factors. Two integer matrices with the same determinant can have different invariant factors and be genuinely different maps, and for a graph’s grounded Laplacian those factors name a group — the critical group — whose order is the tree count and whose shape the spectrum does not fix. The essay called the pair “a candidate for exactly that: same spectrum, same tree count, and a question about the group that the spectrum cannot answer.”

This essay answers the question for that pair and then for every pair it could have been.

The group a spectrum cannot hear #

Remove one vertex’s row and column from a connected graph’s Laplacian and the result is an integer matrix of full rank — the vertex nobody solves for is about that grounding as a numerical device. Its determinant is the number of spanning trees, which is Kirchhoff’s theorem and the computation a count that comes out of a determinant measured. Its Smith normal form is the diagonal matrix $\mathrm{diag}(s_1, \dots, s_{n-1})$, reached by integer row and column operations that can be undone, with each $s_i$ dividing the next. The abelian group $\mathbb{Z}/s_1 \oplus \cdots \oplus \mathbb{Z}/s_{n-1}$ is the critical group of the graph, also called its sandpile group; its elements are the configurations of chips on the vertices, modulo the moves that fire a vertex.

Its order, the product of the $s_i$, is the determinant and so the tree count, and two Laplacian-cospectral graphs share it. How that order splits into factors is not a function of the eigenvalues. The group is therefore a finer invariant than the spectrum in the strict sense: everything the spectrum says about the tree count it says too, and it can say more.

On the pair the earlier essay found, it does. The triangle and the square meet at a single vertex, and a graph built from two blocks joined at a cut vertex has as its group the direct sum of the blocks’ groups: a triangle’s is $\mathbb{Z}_3$, a square’s is $\mathbb{Z}_4$, and $\mathbb{Z}_3 \oplus \mathbb{Z}_4$ is the cyclic group $\mathbb{Z}_{12}$. The other graph is $K_{2,3}$ with an edge hanging off it, and a pendant edge adds nothing — its block is a tree, whose group is trivial — while $K_{2,3}$'s group is $\mathbb{Z}_2 \oplus \mathbb{Z}_6$. Twelve elements both, one cyclic and one not. The Smith forms computed directly agree with both readings: $\mathrm{diag}(1,1,1,1,12)$ against $\mathrm{diag}(1,1,1,2,6)$.

The figure also shows the only other Laplacian-cospectral pair on six vertices, which the earlier essay counted and did not draw. Both graphs have 24 spanning trees, and both groups are $\mathbb{Z}_{24}$. The group cannot separate them, and the reason is as short as the proof above: there is only one cyclic group of each order. Their degree sequences — 3, 3, 3, 3, 3, 1 against 4, 3, 3, 2, 2, 2 — separate them at a glance.

The difference between $\mathbb{Z}_{12}$ and $\mathbb{Z}_2 \oplus \mathbb{Z}_6$ is concrete in the chip-firing reading. The first group has an element of order twelve: a configuration of chips that has to be added to itself twelve times, with every vertex that can fire fired, before it returns to the configuration it started from. In the second, every configuration returns within six additions. Both graphs have exactly twelve recurrent configurations, and in one of them the configurations form a single cycle under addition while in the other they form two interleaved ones. A process that deposits chips one at a time and lets them topple — the sandpile model the group is named for — visits its recurrent states in a different pattern on the two graphs, and the Laplacian spectrum, which governs how fast a random walk on either graph mixes, cannot see the difference.

So on six vertices the finer invariant is one for two.

Every pair on eight vertices #

One for two is not a rate. To get one, every connected graph up to eight vertices is generated exactly once: each graph on $n-1$ vertices has a vertex added in every possible way, and each result is kept only if its canonical form — a relabelling fixed by refining vertices by degree and neighbourhood and then searching exhaustively within the classes that remain — has not been seen. The counts come out as the known ones, 853 connected graphs on seven vertices and 11,117 on eight, which says the generation neither missed nor duplicated a graph. For each, the Laplacian characteristic polynomial is computed exactly, and the Smith normal form of its grounded Laplacian; the product of the factors is required to equal the determinant computed by a different algorithm, for every graph on six and seven vertices.

The Smith form is computed the way it is defined, by integer row and column operations: find the entry of smallest magnitude, move it to the corner, subtract integer multiples of its row and column from the others, and repeat until the corner divides everything left. No division ever leaves the integers, so nothing is rounded and no threshold decides what counts as zero. That is the property that makes the census trustworthy, and it is the property rank is a decision showed a floating-point rank does not have: a Smith factor of two is a fact about the integers, and a singular value of $10^{-15}$ is a judgement about a tolerance.

Grouping by the Laplacian polynomial, eight vertices give 745 classes with more than one member — the largest holds six graphs with the same spectrum — and 1,022 pairs of non-isomorphic graphs inside them. Seven vertices give 55 classes and 65 pairs.

The group separates 30 of the 65 pairs on seven vertices and 435 of the 1,022 on eight — 46% and 43%. The rest divide into two kinds, and the figure keeps them apart because they fail for different reasons. In 23 pairs on seven vertices and 361 on eight, both groups are cyclic; a cyclic group is determined by its order, the order is the tree count, and the tree count is shared, so those pairs could never have been separated by any group computation. In the remaining 12 and 226, both groups are the same non-cyclic group — $\mathbb{Z}_2 \oplus \mathbb{Z}_{2k}$ and the like — and the group simply happens to agree.

Why cyclic groups are the whole limit #

A group is cyclic when the Smith form has at most one factor above one, and most critical groups are. Of the connected graphs on six, seven and eight vertices, 61.6%, 61.0% and 63.6% have a cyclic group. Graphs that have a cospectral mate are less often cyclic — 51.3% on seven vertices, 48.5% on eight — but half of them still are, and a pair of them is out of the group’s reach before any arithmetic is done. For large random graphs the cyclic share tends to about 79%, which is a theorem of Melanie Wood’s; these small graphs sit well below that, and the share is not rising over three to eight vertices, so nothing here suggests the limit loosens soon.

One arithmetic fact sharpens the limit into a rule that can be applied in advance. Every abelian group of squarefree order — an order with no repeated prime factor — is cyclic, because each prime-power part must then be a single $\mathbb{Z}_p$. So when two cospectral graphs share a squarefree tree count, their groups are the same cyclic group, and the tree count alone says so. On eight vertices 157 pairs have a squarefree tree count and the group separates none of them; of the 865 whose tree count has a square factor it separates 435, a half. The group can speak only through repeated primes in the tree count, and a spectrum that has already fixed the tree count has already said how many there are.

Which exact invariant separates the most #

Every invariant in the figure is computed exactly — integers or integer polynomials compared for equality — so no tolerance decides any of these counts, which was the earlier essay’s standard and the reason its pair could be trusted. The normalised Laplacian is left out for exactly that reason: its entries are $-1/\sqrt{d_i d_j}$, it has no integer polynomial, and two Laplacians of one graph shows how differently the two Laplacians can behave on one graph even where both are defined. On eight vertices the degree sequence separates 354 pairs and the triangle count 352, each a little less than the group. The group and the degree sequence together separate 640, 63%: the two are partly independent, and the degree sequence often catches the pairs whose groups are cyclic, as it caught the second six-vertex pair.

Read the other way, that is the group’s own contribution. Of the 640 pairs the two separate together, the degree sequence alone gets 354, so the group adds 286 pairs that no count of degrees could tell apart; on seven vertices it adds 17 to the degree sequence’s 28. A reader who has already compared degree sequences — the cheapest check there is, and the one the earlier essay used first — gains from the group on about a quarter of all cospectral pairs. That is a real gain, and it is the gain a single further integer polynomial beats outright.

The two spectra do far better than any of them, and the reason is information rather than refinement. A spectrum is $n$ numbers, fixed by the traces of the matrix’s powers, and the traces of the adjacency matrix’s powers count closed walks — edges, triangles, squares with their chords, and so on up the lengths — while the traces of the Laplacian’s powers mix those counts with the degrees in a particular way. Two graphs can balance the mixture and not the counts, which is the whole of what a Laplacian-cospectral pair is. The signless Laplacian, $D + A$ rather than $D - A$, separates 906 pairs. The adjacency matrix separates all 1,022 on eight vertices, and all 65 on seven. The earlier essay drew the adjacency spectrum separating its own pair by the triangle count its third moment carries; over the whole census it separates every pair the Laplacian spectrum merges, and it does so while being, like the Laplacian spectrum, a spectrum — the coarser kind of invariant that essay warned against using as an identity.

So the ranking the words suggest is backwards. The group is finer than the Laplacian spectrum, and an order of magnitude less decisive than a second spectrum that is not finer than anything. What the adjacency polynomial adds is independent information; what the group adds is a refinement of one number the Laplacian spectrum already fixed, and a refinement of a number can only say how that number factorises.

A pair that agrees on everything but one coefficient #

Twenty of the pairs on seven vertices share their degree sequence, their triangle count and their group as well as their Laplacian spectrum; the signless Laplacian separates sixteen of those, and the adjacency polynomial all twenty. The pair drawn is one where the signless Laplacian is no help either, and for a structural reason: both graphs are bipartite, and a connected graph’s signless Laplacian has the same spectrum as its Laplacian exactly when it is bipartite. Both have seven edges, degrees 3, 3, 2, 2, 2, 1, 1, no triangles, four spanning trees and group $\mathbb{Z}_4$.

Their adjacency polynomials differ in one coefficient, that of $x$: $-2$ against $0$. Sachs’s theorem reads that coefficient off the graph. It sums over the ways of covering six of the seven vertices by disjoint edges and cycles, counting a set of three disjoint edges as $-1$ and a square with an edge beside it as $+2$. Both graphs have four sets of three disjoint edges, and both have one square. In the graph on the left the square leaves room beside it for one disjoint edge; on the right, for two. That difference — where the one cycle sits relative to the rest — is invisible to the degrees, the triangles, the Laplacian spectrum and the group, and it is the first thing the adjacency polynomial’s lowest terms count.

What the group is for, then #

None of this makes the critical group a poor invariant. It is the right object for the questions it answers: which chip configurations are recurrent, what the Jacobian of a graph is as a discrete analogue of a curve’s, how a graph’s cycle structure sits in an integer lattice. And where it does separate a pair, it separates it by an integer fact that no floating-point computation could establish with certainty — a Smith form is an exact object, and the rank depends on the ring is the reminder that a factor of two in it is invisible to any computation that does not work in the integers or modulo two.

What it is not is a spectral fingerprint’s natural companion. If the aim is to tell graphs apart, a cheap second spectrum does it better on every size measured here; if the aim is to certify that two graphs are the same, neither is enough, and only an isomorphism test is. The group’s distinctive contribution is to Laplacian-cospectral pairs whose tree count has a repeated prime and whose adjacency spectra were not computed, which is a narrow place to stand.

The broader pattern is one this subject meets repeatedly: an invariant that is finer in the lattice-theoretic sense is not thereby more separating over the objects that actually occur. A prime that divides the answer found the same thing from the other side, where reducing modulo a prime can lose information the rational computation kept; here the integer structure is kept and still says little, because the spectrum had already spent most of what it could say.

What eight vertices do not show #

Eight vertices is small, and the ranking can change with size. Pairs of regular graphs — none of which is Laplacian-cospectral at eight vertices or fewer, since the adjacency polynomial would then have failed to separate it — have Laplacian and adjacency spectra that determine each other — $L = kI - A$ — so on them the adjacency polynomial separates nothing the Laplacian did not, and the census here contains no such pair. The critical group is measured only on Laplacian-cospectral pairs; on adjacency-cospectral ones, whose tree counts need not agree, it has an easier task. And the cyclic share is measured, not derived — the 79% limit is for large random graphs, and the graphs that have a cospectral mate are exactly the ones that are not typical.

Still open: nine vertices, regular pairs, and the group’s other job #

Nine vertices. There are 261,080 connected graphs on nine vertices, and generating them the same way is a matter of minutes. The prediction with a sign is that the adjacency polynomial stops separating every Laplacian-cospectral pair there or soon after, at the first pair that is cospectral for both matrices, and that the critical group’s share stays between two fifths and a half because the cyclic share does not move.

Regular pairs. For a $k$-regular graph the three spectra carry the same information, so a regular cospectral pair is the case in which the group is the only exact invariant here that can still speak. How often it does, on the regular cospectral pairs at the smallest sizes where they exist, is the measurement that would say whether the group has a place the spectra cannot reach.

Adjacency-cospectral pairs. The pair the spectrum is not the graph drew first for the adjacency matrix — a square with an isolated vertex against the five-vertex star — is not even connected, and adjacency-cospectral connected pairs need not share a tree count. There the group’s order is free to differ, and the question becomes how often the tree count alone, an integer the adjacency spectrum does not fix, already separates what the adjacency spectrum merges.