## Article Source

## Introduction to Spectral Graph Theory

# A History of Spectral Graph Theory and its Applications

## Abstract

*Spectral graph theory* gives an expression of the combinatorial properties of a graph using the *eigenvalues* and *eigenvectors* of matrices associated with the graph. These ideas were first introduced in the late 80s in order to prove *Cheegerâ€™s inequality* for finding a *sparse cut*. The utility of spectral graph theory eventually stretched to *Laplacian systems* for solving linear equations. Implementing graph sparsification gives us the ability to do this quickly. In this talk we will describe the introduction of the Laplacian matrix and its use in these areas.

## Abstract

Spectral graph theory started in the 80s, when Cheegerâ€™s inequality was used as a means for constructing sparse and balanced cuts in a graph. In the 2000s, our field moved on from studying specific eigenvalues to studying the whole spectrum of the *Laplacian matrix* with fast *Laplacian solvers*. To obtain fast Laplacian solvers, we needed to sparsify graphs, for which we exploited concentration phenomena of random matrices. In the 2010s, improvements to these tools led to improvements on a wide variety of problems, like *maximum flow*, *travelling salesman* (both symmetric and asymmetric), and *random spanning tree generation*.
In this talk, we briefly survey this chain of events and suggest some future directions.