Spectral Graph Theory, Fall 2012

This is the third 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. Isoperimetry, with applications in probability.
  10. Eigenvalues of random graphs.
  11. Finding cliques in and partitioning semi-random graphs.
  12. Testing isomorphism of graphs of bounded eigenvalue multiplicity.
  13. Constructions of higly symmetric graphs: strongly regular graphs and expanders.
  14. Eigenvalues of planar graphs.
  15. The Colin de Verdière number of a graph.
  16. Spectral theory for directed graphs.
The work for the course will consist of 5 or 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.