Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Seen this? Or this? –  J. M. Nov 8 '11 at 13:55
    
@J.M. Thanks. I will look at these. I'm not sure the second one applies. But, the first one seems to be a good one. –  Graphth Nov 10 '11 at 21:26

2 Answers 2

up vote 4 down vote accepted
+50

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.

share|improve this answer
    
Thanks, I will check this out! –  Graphth Nov 10 '11 at 21:14

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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.