Graphs with eigenvalues of large multiplicity

Question

For a strongly regular graph, there are exactly 3 eigenvalues, all nonzero (I believe). One has multiplicity 1, which means the other two have pretty high multiplicities. There are tables that give these eigenvalues and multiplicities:

http://www.win.tue.nl/~aeb/graphs/srg/srgtab1-50.html

For example, the Schlaefli graph is order 27 but has an eigenvalue of order 20.

My question is, are there other known graphs (families, types, or just single graphs) that have large multiplicities of eigenvalues? When I check a random graph in Sage, it seems the max multiplicity is mostly 1.

Answer 1

One class of examples are distance-regular graphs; strongly regular graphs are (essentially) distance-regular graphs with diameter. Distance-regular graphs can be constructed from Hadamard matrices, symmetric designs and linear codes.

If all eigenvalues of the adjacency matrix $A$ of a graph are simple, then any matrix $P$ that commutes with $A$ must be a polynomial in $A$. It follows from this that all automorphisms have order dividing two, and also that the graph either is the complete graph $K_2$ or cannot be vertex transitive So any vertex-transitive on more than two vertices has an eigenvalue which is not simple.

You can learn about these things in Biggs's ``Algebraic Graph Theory'', for example.

Answer 2

Random graphs are likely to have distinct eigenvalues because their characteristic polynomials are random, and random polynomials are likely to have nonzero discriminant. I'm sure this can be made precise but I'm not the one to do it.

In any case, you want graphs which are far from random. Your best bet is to find graphs with nonabelian automorphism groups. This is because the automorphism group $G$ of a graph acts on each of the eigenspaces of its adjacency matrix, so in particular if $V$ denotes the set of vertices then the irreducible representations of $G$ that occur in $\mathbb{C}^V$ must all lie in eigenspaces, hence their dimensions give lower bounds on the multiplicities of the eigenvalues.

The easiest way to construct graphs with this property is to use Schreier graphs, which are generalizations of Cayley graphs. You want to pick a group $G$ and a $G$-set $S$ such that $\mathbb{C}^S$ has irreducible subrepresentations of large dimension. One way to do this is to pick $G$ such that all of its nontrivial irreducible representations have large dimension, e.g. the groups $\text{PSL}_2(\mathbb{F}_q)$.