What happens if you diagonalize the adjacency matrix of a graph? The study of this question is the province of "spectral graph theory," and it makes interesting, beautiful, and useful connections between linear algebra and graph theory.

I will survey some basic results in spectral graph theory and discuss the relationship between the spectrum of a graph, expansion properties, and random walks on a graph. Then we'll turn our attention to algorithms for "spectral partitioning."

First introduced by Fiedler, these algorithms use the second smallest eigenvector of the Laplacian of a graph to find good graph separators. I'll give some applications of spectral partitioning and sketch a result due to Spielman and Teng that shows "spectral partitioning works" for the case of planar graphs.