Article Source

• Title: A History of Spectral Graph Theory and its Applications

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.