Spectral Graph Theory, Fall 2009

Applied Mathematics 561/ Computer Science 662

Instructor: Dan Spielman.

Time: W-F 2:30-3:45

Recommended book: Algebraic Graph Theory by Chris Godsil and Gordon Royle

This is the second time I am teaching this course.  To get a feeling for what the class is going to be like, I recommend looking at The topics for this year's course will include:
  1. Eigenvalues and eigenvectors of common graphs: paths, trees, cliques, grids, products.
  2. Random walks on graphs.
  3. Eigenvalues and the diameter of a graph.
  4. Cheeger's inequality.
  5. Hoffman's bound on the size of an independent set in a graph.
  6. Approximations of graphs and sparsification.
  7. Low-stretch spanning tress and generalized eigenvalues of graphs.
  8. Expander graphs, with applications in coding theory and derandomization.
  9. Eigenvalues of random graphs.
  10.  Finding cliques in and partitioning semi-random graphs.
  11. Testing isomorphism of graphs of bounded eigenvalue multiplicity.
  12. Constructions of special graphs: strongly regular graphs and expanders.
  13. Eigenvalues of planar graphs.
  14. The Colin de Verdière number of a graph.
  15. Spectral theory for directed graphs.
The work for the course will consist of approximately 6 problem sets.

This course will assume familiarity with graphs and linear algebra.  While this background knowledge is
elementary, the course will move at a fast pace.  This course may be suitable for advanced undergraduates.
Undergraduate students who are interested in taking the course are advised to consult with the instructor
before registering.