Why do we care about eigenvalues of graphs?

Of course, any novel question in mathematics is interesting, but there is an entire discipline of mathematics devoted to studying these eigenvalues, so they must be important.

I always assumed that spectral graph theory extends graph theory by providing tools to prove things we couldn’t otherwise, somewhat like how representation theory extends finite group theory. But most results I see in spectral graph theory seem to concern eigenvalues not as means to an end, but as objects of interest in their own right.

I also considered practical value as motivation, e.g. using a given set of eigenvalues to put bounds on essential properties of graphs, such as maximum vertex degree. But I can’t imagine a situation in which I would have access to a graph’s eigenvalues before I would know much more elementary information like maximum vertex degree.

(

EDIT:for example, dtldarek points out that λ2 is related to diameter, but then why would we need λ2 when we already have diameter? Is this somehow conceptually beneficial?)So, what is the meaning of graph spectra intuitively? And for what practical purposes are they used? Why is finding the eigenvalues of a graph’s adjacency/Laplacian matrices more than just a novel problem?

**Answer**

This question already has a number of nice answers; I want to emphasize the breadth of

this topic.

Graphs can be represented by matrices – adjacency matrices and various flavours of

Laplacian matrices. This almost immediately raises the question as to what are

the connections between the spectra of these matrices and the properties of the

graphs. Let’s call the study of these connections “the theory of graph spectra”.

(But I am not entirely happy with this definition, see below.) It is tempting to view the map

from graphs to eigenvalues as a kind of Fourier theory, but there are difficulties

with this analogy. First, graphs in general are not determined by the their eigenvalues.

Second, which of the many adjacency matrices should we use?

The earliest work on graph spectra was carried out in the context of the Hueckel

molecular orbital theory in Quantum Chemistry. This lead among other things to work

on the matching polynomial; this gives us eigenvalues without adjacency matrices

(which is why I feel the above definition of the topic is unsatisfactory). A more recent

manifestation of this stream of ideas is the work on the spectra of fullerenes.

The second source of the topic arises in Seidel’s work on regular two-graphs,

which started with questions about regular simplices in real projective space

and lead to extraordinarily interesting questions about sets of equiangular lines

in real space. The complex analogs of these questions are now of interest to quantum

physicists – see SIC-POVMs. (It is not clear what role graph theory can play here.)

In parallel with Seidel’s work was the fundamental paper by Hoffman and

Singleton on Moore graphs of diameter two. In both cases, the key observation was

that certain extremal classes of graphs could be characterized very naturally

by conditions on their spectra. This work gained momentum because a number of sporadic

simple groups were first constructed as automorphism groups of graphs. For graph

theorists it flowered into the the theory of distance-regular graphs, starting with

the work of Biggs and his students, and still very active.

One feature of the paper of Hoffman and Singleton is that its conclusion makes no reference

to spectra. So it offers an important graph theoretical result for which the “book proof”

uses eigenvalues. Many of the results on distance-regular graphs preserve this feature.

Hoffman is also famous for his eigenvalue bounds on chromatic numbers, and related

bounds on the maximum size of independent sets and cliques. This is closely related

to Lovász’s work on Shannon capacity. Both the Erdős-Ko-Rado

theorem and many of its analogs can now be obtained using extensions of these techniques.

Physicists have proposed algorithms for graph isomorphism based on the spectra of

matrices associated to discrete and continuous walks. The connections between

continuous quantum walks and graph spectra are very strong.

**Attribution***Source : Link , Question Author : Alexander Gruber , Answer Author : Chris Godsil*