How do eigenvalues of combinatorial Laplacian relates to automorphisms in graphs?

Question

Is there a relation between eigenvalues of the graph Laplacian and the automorphism group of a simple graph?

How are the multiplicities of Laplacian eigenvalues related to the order of the automorphism group?

Answer 1

For $v=6k+1$ or $v=6k+3$ and $k$ not extremely small there are a great many ways to make a Steiner Triple System with $v$ objects and $M=\frac{v(v-1)}6$ triples so that each pair of objects is in a unique triple. We call this an $STS(v)$. The block graph of an $STS(v)$ has $M$ vertices labeled by the triples. It is regular of degree $k=\frac{3(v-1)}2$ with two vertices connected by an edge if the triples share a member. Some of this have a huge symmetry group but most are rigid (no non-trivial automrphisms.)

One hugely symmetric case is to take $v=2^j-1$ and consider the $v$ non-zero binary vectors of length $j$ other than the zero vector $\mathbf{0}.$ The triples are the $T=\{x,y,z\}$ with $x+y+z=\mathbf{0}.$

In any case, the spectrum is quite simple. The Laplacian spectrum is $0,v,k+3$ with multiplicities $1,v-1,\frac{v(v-7)}6.$

However there are tremendous number of ways to get a $STS(v)$. The corresponding block graphs all have the same spectrum but most of them have no automorphisms. There are also graphs with the same spectrum which do not come from an STS (I don't know much about them). One available source for information is here.

There are $11,084,874,829$ strongly regular graphs with parameters SRG$(57,24,11,9)$ which arise from a Steiner triple system with $19$ points (and $57$ blocks); Of these $11,084,710,071$ are rigid. The article I linked to says that there are more than that many with the same parameters but not coming from a STS.

Answer 2

I think you can more or less only go in one direction here: a large amount of symmetry can imply few eigenvalues. Intuitively, this makes sense because if $f: V(G) \to \mathbb{R}$ is an eigenvector for the Laplacian of $G$ with eigenvalue $\lambda$ and $\pi$ is an automorphism, then $f \circ \pi$ is an eigenvector with the same eigenvalue. So lots of automorphisms should mean large eigenvalue multiplicities and thus fewer eigenvalues. But making this rigorous is of course more difficult. There are probably several ways to do it but here is one:

Let $\mathrm{Aut}(G)$ be the automorphism group of the graph $G$. We refer to the orbits of $\mathrm{Aut}(G)$ on $V(G) \times V(G)$ as the orbitals of $\mathrm{Aut}(G)$ (or just of $G$). For each orbital we can construct an orbital matrix which has rows and columns indexed by $V(G)$ and has a 1 in the $uv$-entry if $(u,v)$ is in that orbital. These matrices span an algebra (in fact they span something called a coherent algebra), and this algebra is actually the commutant of $\mathrm{Aut}(G)$ represented as permutation matrices. Since the Laplacian of $G$ (I'll call it $L(G)$) must commute with the automorphisms of $G$ (represented as matrices), it must lie in the commutant of $\mathrm{Aut}(G)$, i.e., in the span of the orbital matrices of $G$. Since the commutant is an algebra this also holds for any polynomial in $L(G)$, and so the dimension of the algebra generated by $L(G)$ is at most the dimension of the commutant of $\mathrm{Aut}(G)$. The former is the number of distinct eigenvalues of $L(G)$ and the latter is the number of orbitals of $\mathrm{Aut}(G)$. So the number of distinct eigenvalues of the Laplacian of $G$ is at most the number of orbitals of $G$.

But we can actually do better. The coherent algebra of a graph $G$ is the smallest matrix algebra that is closed under conjugate transposition and entrywise product, and contains the adjacency matrix of $G$, the identity matrix, and the all ones matrix. This algebra is a subalgebra of the commutant of $\mathrm{Aut}(G)$, but it is not hard to see that $L(G)$ must lie in this subalgebra. Therefore the dimension of this subalgebra is a (possibly better) upper bound on the number of distinct eigenvalues of $L(G)$.

The coherent algebra of $G$ has a unique basis of 01-matrices which correspond to a partition of $V(G) \times V(G)$, and the number of parts of the partition is equal to the dimension of the coherent algebra. This partition is necessarily a coarse-graining of the partition given by the orbitals of $\mathrm{Aut}(G)$. In the case of a strongly regular graph $G$, this partition has only three parts corresponding to the vertices, edges, and non-edges of $G$. This is why strongly regular graphs only have three distinct eigenvalues, even if they have no non-identity automorphisms.

Note that all of the above also works for the adjacency matrix of a graph, or several other matrices associated to graphs such as the signless or normalized Laplacian.