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.