Comment

Comment by actually_a_dog

You're right, of course. I should have said that the spectrum isn't all that useful for telling two graphs of the same order apart. Certain eigenvalues are frequently useful by themselves (e.g. the largest, second largest, and smallest eigenvalues often contain some information).

But, speaking of information, consider this: the adjacency matrix of a simple, loopless graph of order n is a symmetric n x n matrix with all zeroes on the diagonal. That means the adjacency matrix contains (literally) n^2/2 - n bits of information, while the number of connected graphs of order n as n -> infinity grows exponentially [0]. That implies that for the purpose of telling two graphs of the same order apart, the spectrum is of fairly limited utility, which is what I was thinking of when I wrote that it was not an interesting invariant.

---

[0]: https://users.cecs.anu.edu.au/~bdm/papers/BCM_Connected1.pdf

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton