Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question is motivated by a talk I went to earlier today.

Suppose we have a $d$-regular graph $G$ with $n$ vertices, with adjacency matrix $A$.

Let $$\lambda_1\geq \lambda_2 \geq\dots \geq \lambda_n$$ be the eigenvalues of $A$, so in particular $\lambda_1=d$. If the first two eigenvalues are the same, that is $\lambda_2=\lambda_1$, then it tells us a lot about the structure of the graph. In particular, the graph must be disconnected. (This is an if and only if condition)

What if the second and third eigenvalues are equal? That is, suppose that $\lambda_1>\lambda_2=\lambda_3$. What does that tell us (if anything) about the structure of the graph?

Additional questions: If $\lambda_1=\lambda_2=\cdots=\lambda_k<\lambda_{k+1}$, then the graph will have exactly $k$ connected components. What can we say about $G$ if $\lambda_1<\lambda_2=\cdots=\lambda_{k+1}<\lambda_{k+2}$? That is, the second eigenvalue has multiplicity $k$.

What if the $n^{th}$ eigenvalue has multiplicity $k$?

share|improve this question
1  
The $d$-eigenspace is rather special. It corresponds to the kernel of the Laplacian which can be naturally identified with the space of locally constant functions on $g$ ("harmonic functions"). A similar interpretation doesn't exist for smaller eigenvalues so I don't expect their multiplicities to have a similar direct meaning. However, large multiplicities of eigenvalues in general suggest (but don't imply) that $G$ has nontrivial symmetries. –  Qiaochu Yuan Jul 4 '12 at 19:52
    
@Qiaochu: Here is one example which may count. If $\lambda_2$ has multiplicity $n-1$, that is all other eigenvalues are the same, then I believe that $G$ must be the complete graph. –  Eric Naslund Jul 4 '12 at 20:55
1  
It would imply that the graph can be "partitioned" into two weakly connected components, in two different ways. –  Piyush Grover May 31 '13 at 20:21
    
Such results are studied in machine learning and dynamical systems communities, under various terms such as "spectral clustering", "Almost-invariant sets", "metastable sets" etc. They look at the eigenspectrum of graph Laplacian, rather than the Adjacency matrix itself, though. –  Piyush Grover May 31 '13 at 20:24
add comment

1 Answer

It you allow weighted adjacency matrices and if you insist (among there things) that the eigenspace associated to $\lambda_2$ satisfies the "strong Arnold condition", then you are dealing the Colin de Verdiere invariant. For this, the best I can do now is to refer you to the wikipedia article on this invariant.

But you question is what can be said about connected graphs where $\lambda_1$ has multiplicity greater than one. The short answer is: very little. One reason for this that if our graph was associated with some physical of chemical system, than having $\lambda_2$ very close to $\lambda_3$ will have much the same effect as having $\lambda_2=\lambda_3$. There are certainly no results on graph spectra that relate properties of a graph to whether or not $\lambda_2$ is simple.

It is true that the existence of non-trivial automorphisms can prevent all eigenvalues from being simple. The classic result of this type is that if the automorphism group of a graph is vertex transitive, then its eigenvalues can not all be simple. Stronger assumptions may give more, since each eigenspace provides a representation of the automorphism group, and if one of these representations is faithful, then the multiplicity is at least the minimum degree of an irreducible representation of the group.

On the other hand though, having eigenvalues of large multiplicity tells us nothing about the automorphism group. Strongly regular graphs have large multiplicities, but in general no non-trivial automorphisms.

share|improve this answer
add comment

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.