Student Combinatorics Seminar

Given a graph G, there are (at least) two natural matrices one can associate to it: the adjacency matrix and the Laplacian. Spectral graph theory studies the relationship between the eigenvalues of these matrices and properties of G. In this talk we will sample some basic results in this direction to get a taste of the "flavor" of the field. Of particular interest and among the things to be discussed in this talk is the relationship between the second smallest eigenvalue of the Laplacian and the so-called isoperimetric constant, which gives a quantitative measure of the connectivity of G. This relationship is a close analogue of Cheeger's inequality in Riemannian geometry. Speaker(s): Carsten Peterson (University of Michigan)