Seminar

The Spectral Gap of a Graph

Paul Horn
Graduate Student, Department of Mathematics, UCSD

Wednesday, May 7th, 2008
Sage 2707, 11:00 am to 12:00 pm

Abstract:

The spectrum of a graph allows great insight on many important graph properties; among them discrepancy, expansion and the mixing time of random walks. An advantage of looking at the spectrum is that it can, in fact, be computed efficiently and allows us a way of guaranteeing expansion (which in general is NP-hard to compute). In this talk, we discuss various graph spectra and their uses and then focus on the spectrum of a normalized Laplacian whose spectrum captures information about graphs which have arbitrary degree sequences. We establish bounds showing that the spectral gap of a random subgraph of a graph is close to that of the original graph. We then turn to the question of how 'good' can the spectral gap of a graph be, giving an answer which generalizes a classical theorem of Alon and Boppana for regular graphs to graphs with an arbitrary degree sequence. Some of this work is joint work with Fan Chung.

Hosted by: Mark Goldberg (x2609)

Administrative support: Chris Coonrad (x8412) and Shannon Carrothers (x6354)

For more information:

Paul Horn's Homepage at UCSD

Last updated: 5/2/2008