6
$\begingroup$

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$?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Jul 4, 2012 at 19:52
  • $\begingroup$ @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. $\endgroup$
    – Eric Naslund
    Commented Jul 4, 2012 at 20:55
  • 2
    $\begingroup$ It would imply that the graph can be "partitioned" into two weakly connected components, in two different ways. $\endgroup$
    – Piyush Grover
    Commented May 31, 2013 at 20:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – Piyush Grover
    Commented May 31, 2013 at 20:24
  • 1
    $\begingroup$ @PiyushGrover Hey sorry for such a comment after such a long time but could have any references about your comment about partitioning $\endgroup$
    – rostader
    Commented Oct 18, 2021 at 22:47

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .