Each spectrum hears the other's pairs

A finer invariant that hears less took every connected graph on up to eight vertices, found every pair with the same Laplacian characteristic polynomial, and asked what tells the two graphs of a pair apart. The candidate was the critical group — the abelian group named by the Smith normal form of the grounded Laplacian, whose order is the number of spanning trees. Two Laplacian-cospectral graphs share their tree count, since the matrix-tree theorem makes it the product of the nonzero Laplacian eigenvalues over n, so the group could only separate them by how that common number factors. At eight vertices it did on 435 of 1,022 pairs. The degree sequence managed 354 and the triangle count 352; the signless Laplacian’s polynomial managed 906; the adjacency polynomial separated all 1,022.

The essay’s last question was the census run the other way. “The pair the spectrum is not the graph drew first for the adjacency matrix … 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, separates them.”

The census, turned round #

The method is the earlier essay’s. Every graph on up to eight vertices is generated once up to isomorphism — 12,346 at eight, of which 11,117 are connected — and for every connected one the adjacency, Laplacian and signless-Laplacian characteristic polynomials are computed exactly in integers, as is the Smith form of the grounded Laplacian. What changes is the key the graphs are grouped by: now two graphs are a pair when their adjacency polynomials agree.

There is one such pair at six vertices, thirty-three at seven in thirty-one classes, and 733 at eight in 659 classes, the largest of which holds four graphs. That is fewer than the Laplacian side’s 1,022 at eight, and the asymmetry is itself a finding the census did not set out to make: on small connected graphs the Laplacian spectrum is the weaker fingerprint.

The six-vertex pair is small enough to read whole. Both graphs have seven edges and two triangles, which their shared spectrum forces — the trace of $A^2$ is twice the edge count and the trace of $A^3$ is six times the triangle count. Everything else differs. One has a vertex of degree five and nine spanning trees; the other is four vertices of degree three and two of degree one, with eight. Their critical groups are $\mathbb{Z}_3 \oplus \mathbb{Z}_3$ and $\mathbb{Z}_8$ — not merely different groups but different orders, which on the Laplacian side was impossible by construction.

Each spectrum separates the other’s pairs #

The figure at the top of the page sets the two censuses side by side at eight vertices. On the Laplacian pairs, the bars are the earlier essay’s. On the adjacency pairs, the Laplacian polynomial separates all 733 — every one — and so does the signless Laplacian’s. The adjacency polynomial separated every Laplacian pair; the Laplacian polynomial separates every adjacency pair. At these sizes no two connected graphs share both spectra.

That is a stronger statement than either census makes alone. Two matrices built from one graph, $D - A$ and $A$, differ by the degree matrix, and the degree matrix is exactly what each spectrum is blind to in a different way: the adjacency spectrum fixes the number of edges but not how they are distributed over vertices, and the Laplacian spectrum fixes the tree count but not the triangle count. A matrix with no numbers in it described the two as two questions asked of one object. Measured, the two answers are complementary to the last pair at eight vertices: whatever one spectrum leaves together, the other separates.

The other invariants line up the same way. The triangle count, fixed by the adjacency spectrum, separates none of the adjacency pairs and a third of the Laplacian ones. The tree count, fixed by the Laplacian spectrum, separates none of the Laplacian pairs and nearly all of the adjacency ones. The degree sequence, fixed by neither, separates 35 per cent of Laplacian pairs and 83 per cent of adjacency pairs.

How much each spectrum determines alone #

The pairs are the failures; the census also counts the successes. A graph is determined by a spectrum when no other graph in the census shares it, and the share of connected graphs each spectrum determines is the measure of how good a fingerprint it is.

At eight vertices the adjacency spectrum determines 9,764 of the 11,117 connected graphs, 87.8 per cent; the Laplacian spectrum 9,506, 85.5 per cent; the signless Laplacian 10,070, 90.6 per cent. At seven the order is different — adjacency 92.6, signless 90.6, Laplacian 86.5 — and at six different again, with the signless Laplacian the worst at 102 of 112. No one of the three is the best fingerprint at every size, and each alone leaves one connected graph in ten or more with a mate.

What the three do together is not symmetric. No pair at any size shares its adjacency spectrum with either Laplacian spectrum: the adjacency spectrum and either Laplacian, taken together, determine every connected graph on up to eight vertices. The two Laplacians are not so complementary. Eight pairs at seven vertices and 116 at eight share both, so a graph’s combinatorial and signless Laplacian spectra together still leave 116 pairs at eight vertices unresolved — pairs that the adjacency spectrum, the weakest of the three on the Laplacian side’s own census of failures, separates every one of.

Part of that is a familiar identity. On a bipartite graph $D - A$ and $D + A$ are similar — conjugate by the diagonal matrix of $\pm 1$ that flips one side — so a bipartite graph’s two Laplacian spectra are one spectrum, and any pair of bipartite graphs cospectral for one Laplacian is cospectral for the other. But it is a small part: of the 116 pairs at eight vertices that share both Laplacian spectra, six are pairs of bipartite graphs, and of the eight at seven vertices, two. The other 110 share both spectra with no identity forcing it. The adjacency matrix shares no such coincidences with either Laplacian at these sizes, and the census does not say why; it says only that it does not.

One integer does nearly all of it #

The earlier essay’s question has a plain answer. At seven vertices the tree count separates thirty of the thirty-three adjacency pairs; at eight, 717 of the 733 — 97.8 per cent — with sixteen pairs left on the diagonal. A single integer, computable as one determinant, tells apart nearly every pair of graphs that the whole adjacency spectrum cannot.

The count is cheap and exact. It is the determinant of the grounded Laplacian — the Laplacian with one vertex’s row and column removed, the step the vertex nobody solves for measured as the standard way to remove the Laplacian’s kernel — and it is the same number every effective resistance on the graph is divided by: the resistance across an edge is the share of spanning trees that use it, which a distance computed by a solve computed by a linear solve instead. An invariant that sits under that much of the Laplacian’s behaviour separating 98 per cent of the pairs the adjacency spectrum confuses is less surprising, put that way, than it first sounds.

At seven vertices the picture is the same in miniature. The thirty-three pairs fall into thirty-one classes, two of them triples; the tree counts differ on thirty, with a median ratio of 1.100, and the three pairs that share a count share it at 8, 21 and 40 spanning trees. Forty admits three abelian groups and both graphs of that pair have the cyclic one. In all three the degree sequences differ in the same way — one graph has a vertex of degree five, the other two of degree four — so at seven vertices the degrees separate every adjacency pair and at eight they stop doing so.

It does so by a narrow margin. The cloud in the figure hugs the diagonal, and the margins are measurable:

The ratio of the two counts runs from 1.0008 to 1.50, with a median of 1.060; 461 of the 717 pairs differ by less than ten per cent. Two graphs with the same adjacency spectrum have the same number of edges and nearly the same structure in every respect the spectrum constrains, so their tree counts — which grow very fast with the edge count, and here sit between one and a few thousand — are close. But an integer that is close is still an integer, and two tree counts that differ by one part in twelve hundred, as the closest pair’s do, are as decisively different as two that differ by half.

That is the property that makes the count a good invariant here and a useless one on the other side. On Laplacian pairs it is identical by construction. On adjacency pairs it is almost never identical, because nothing ties it to the adjacency spectrum except the edge count, and a function of many things that agrees with one of them only by coincidence rarely agrees by coincidence.

The degree sequence is the other invariant both censuses measured, and it tells apart a different selection of pairs. Of the 733 adjacency pairs at eight vertices, 605 have different degree sequences and 717 different tree counts; 125 are told apart by the tree count and not by the degrees, 13 by the degrees and not by the tree count, and 3 by neither. So the count is not a stand-in for the degrees — a pair with the same degrees has nearly the same edge distribution, and the tree count still differs on 125 such pairs. Where both fail, only the Laplacian spectra are left.

The group adds nothing the count does not #

The critical group was the candidate that heard more than the spectrum on the Laplacian side, and on the adjacency side it has every opportunity: its order can differ, and when its order agrees it can still factor differently. It separates exactly the 717 pairs the tree count separates. On all sixteen pairs whose counts agree, the two graphs have the same group.

Some of the sixteen could not have been separated by the group. Their tree counts are 1, 3, 3, 4, 4, 4, 8, 8, 21, 21, 24, 32, 120, 120, 511 and 545, and seven of those — 1, 3, 3, 21, 21, 511 and 545 — are squarefree, so the only group of that order is cyclic and equal counts mean equal groups automatically. The other nine have room in them. Four admits $\mathbb{Z}_4$ or $\mathbb{Z}_2 \oplus \mathbb{Z}_2$, and on all three pairs at four both graphs are $\mathbb{Z}_4$. Eight, 24 and 120 each admit three abelian groups, and on all five of those pairs both graphs have the cyclic one. Thirty-two admits seven, and the one pair at thirty-two has $\mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_8$ on both sides. Where the group could have heard a difference the count missed, nine times, it did not.

So the two directions differ in exactly the way the earlier essay’s account predicts. On the Laplacian side, the group’s order is fixed and the group is the only place a difference can hide, and it is found there two times in five. On the adjacency side, the order is free, and a difference that exists shows up in the order: the group’s finer structure has nothing left to add. The group is finer than the count as an invariant of a graph and no finer as an invariant of an adjacency-cospectral pair, at these sizes.

The sixteen are also where the census reaches its last resort. Three of them — at four, 511 and 545 spanning trees — share their degree sequence as well, and on those three the only invariants here that separate the two graphs are the Laplacian and signless-Laplacian spectra. The pair at one spanning tree is two trees on eight vertices with the same adjacency spectrum: cospectral trees exist from eight vertices, and a tree has exactly one spanning tree, so the count is no help with them by definition.

What this says about hearing a graph #

The spectrum is not the graph began this line of argument with the observation that a spectrum does not determine its graph. The census says how far that goes on small connected graphs and how quickly a second spectrum closes the gap. Neither spectrum alone determines a connected graph on seven or eight vertices; the two together determine every one at these sizes, because there is no pair they share. And the integers the Laplacian side cannot use — the tree count above all — do most of the work on the adjacency side for the price of one determinant.

Two Laplacians of one graph found the combinatorial and the normalised Laplacians answering different questions about one graph. The same holds of the adjacency and Laplacian spectra, measured as fingerprints: they are blind in complementary places, and that complementarity is complete at eight vertices.

All of these fingerprints are exact, and that is a condition worth stating, because most of what is done with Laplacians in practice is approximate. A graph with a tenth of the edges kept every Laplacian eigenvalue of a graph to within a factor of 1.7 with a tenth of its edges, which is the right guarantee for a solver and no guarantee at all for a fingerprint: two graphs whose spectra agree to a factor of 1.7 can be any two graphs of similar density. The census works because its polynomials have integer coefficients and are compared exactly, and because its tree counts and groups are integers. Computed in floating point, two spectra would be compared to a tolerance, and the 0.08 per cent between the closest pair of tree counts here would be a judgement about that tolerance rather than a fact.

What eight vertices do not show #

The census stops at eight because the enumeration does: 261,080 connected graphs on nine vertices would take the canonical-form search the earlier essays used several times longer, and the claim that no connected graph pair shares both spectra is known to fail at larger sizes — pairs cospectral for both matrices exist, and among regular graphs every adjacency-cospectral pair is Laplacian-cospectral too, since the Laplacian of a regular graph is a shift of its adjacency matrix. No pair the census found is a regular pair — it could not be, since the Laplacian separates every one — and that is part of why the two spectra separate so cleanly here. The group computation is exact; the claim that the group adds nothing is about these 733 pairs and not a theorem.

Still open: nine vertices, and the regular pairs where both spectra are one #

Nine vertices. The prediction with a sign the earlier essay made — that the adjacency polynomial stops separating every Laplacian-cospectral pair at nine vertices, at the first pair cospectral for both matrices — has a mirror here: that the Laplacian stops separating every adjacency pair at the same size, by the same pair. Whether the first doubly cospectral connected pair is regular, and whether the tree count and the group separate it, is the measurement that would say whether this page’s complementarity is a small-graph accident.

Regular cospectral pairs. 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.