Motivation for spectral graph theory.

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

Leave a Comment