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 $\lambda_2$ is related to diameter, but then why would we need $\lambda_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?

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.

I can't speak much to what traditional Spectral Graph Theory is about, but my personal research has included the study of what I call "Spectral Realizations" of graphs. A spectral realization is a special geometric realization (vertices are not-necessarily-distinct points, edges are not-necessarily-non-degenerate line segments, in some $\mathbb{R}^n$) derived from the eigenvectors of a graph's adjacency matrix.

In particular, if the rows of a matrix constitute a basis for some eigenspace of the adjacency matrix a graph $G$, then the columns of that matrix are coordinate vectors of (a projection of) a spectral realization.

A spectral realization of a graph has two nice properties:

• It's harmonious: Every graph automorphism induces to a rigid isometry of the realization; you can see the graph's automorphic structure!
• It's eigenic: Moving each vertex to the vector-sum of its immediate neighbors is equivalent to scaling the figure; the scale factor is the corresponding eigenvalue.

Well, the properties are nice in theory. Usually, a spectral realization is a jumble of collapsed segments, or is embedded is high-dimensional space; such circumstances make a realization difficult to "see". Nevertheless, a spectral realization can be a helpful first pass at visualizing a graph. Moreover, a graph with a high degree of symmetry can admit some visually-interesting low-dimensional spectral realizations; for example, the skeleton of the truncated octahedron has this modestly-elaborate collection:

For a gallery of hundreds of these things, see the PDF linked at my Bloog post, "Spectral Realizations of Graphs".

Since many mathematical objects decompose into eigen-objects, it probably comes as no surprise that any geometric realization of a graph is the sum of spectral realizations of that graph. (Simply decomposing the realization's coordinate matrix into eigen-matrices gets most of the way to that result, although the eigen-matrices themselves usually represent "affine images" of properly-spectral realizations. The fact that affine images decompose into a sum of similar images takes an extension of a theorem of Barlotti.) There's likely something interesting to be said about how each spectral component spectral influences the properties of the combined figure.

Anyway ... That's why I care about the eigenvalues of graphs.

Spectral graph theory is a discrete analogue of spectral geometry, with the Laplacian on a graph being a discrete analogue of the Laplace-Beltrami operator on a Riemannian manifold. The Laplacian $\Delta$ can be used to write down three important differential equations, both on a graph and a Riemannian manifold:

• The heat equation $\frac{\partial u}{\partial t} = \Delta u$, which describes how heat propagates on the graph / manifold,
• The wave equation $\frac{\partial^2 u}{\partial t^2} = \Delta u$, which describes how waves propagate on the graph / manifold,
• The Schrödinger equation $i \frac{\partial u}{\partial t} = \Delta u$, which describes how quantum particles propagate on the graph / manifold.

The behavior of solutions to these equations is controlled by the eigenvalues of the Laplacian. For the heat equation these eigenvalues control the rate at which a given heat distribution decays to a stationary distribution, and for the wave and Schrödinger equations these eigenvalues control the rate at which standing wave solutions oscillate (this gives some intuition as to why the eigenvalues should be related to the connectivity of the graph). So these eigenvalues describe some important physical properties of the graph / manifold.

Some random facts:

• The largest eigenvalue $\lambda_1$ is closely related to average degree.
• The second largest eigenvalue $\lambda_2$ is closely related to connectivity, that is graphs with small $\lambda_2$ have small diameter.
• A graph $G$ is bipartite if and only if for every eigenvalue $\lambda$, $-\lambda$ is also an eigenvalue.
• For connected $G$, the chromatic number of $G$, $\chi(G) \leq \lambda_1+1$, with equality for $G$ being complete or an odd cycle.
• Some use spectrum for clustering.

I hope it helps ;-)