A History of Spectral Graph Theory and its Applications, Part I

Nick Ryder (Mathematics, UC Berkeley) 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. License: CC BY-NC-SA 4.0 https://creativecommons.org/licenses/...