Spectral Graph Theory, Fall 2009

Applied Mathematics 561/ Computer Science 662

Instructor: Dan Spielman.
Teaching Assistant: Andrei Osipov, office hours Monday 10:25-11:25 and Thursday 11:45-12:45, in AKW 114

Time: W-F 2:30-3:45, in AKW 500 (51 Prospect Street)

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

Here is the course announcement.

Lecture Notes:

  1. Sept 2, 2009: course introduction (postscript)
  2. Sept 4, 2009: Introduction to The Laplacian (postscript)
  3. Sept 9, 2009: Laplacians and Adjacency Matrices (postscript)
  4. Sept 11, 2009: Courant-Fischer and Graph Coloring (postscript)
  5. Sept 16, 2009: Other eigenvectors of the Laplacian (postscript)
  6. Sept 18, 2009: Graphic Inequalities (postscript)
  7. Sept 23, 2009: Cheeger's Inequality (postscript)
  8. Sept 25, 2009: Random Walks on Graphs (postscript)
  9. Sept 30, 2009: Pseudo-Random Generators from Random Walks on Expanders (postscript)
  10. Oct 2, 2009: Properties of Expander Graphs (postscript)
  11. Oct 7, 2009: Introduction to Error-Correcting Codes (postscript)
  12. Oct 9, 2009: Error-Correcting Codes from Expanders (postscript)
  13. Oct 14, 2009: Algebraic Constructions of Graphs (postscript)
  14. Oct 16, 2009: The Simplest Construction of Expanders (postscript)
  15. Oct 21, 2009: Iterative solvers for linear equations (postscript)
  16. Oct 23, 2009: Preconditioning Laplacians by Low-Stretch Trees (postscript)
  17. Oct 28, 2009: Guest lecture by Nikhil Srivastava on Sparsification
  18. Oct 30, 2009: Guest lecture by Nikhil Srivastava on things Nikhil thinks you should know, that Dan didn't cover.
  19. Nov 4, 2009: Diameter, Probability, and Concentration of Measure (postscript)
  20. Nov 6, 2009: Spectra of Random Graphs (postscript)
  21. Nov 11, 2009: Spectral Partitioning in the Planted Model (postscript)
  22. Nov 13, 2009: Testing Isomorphism of Graphs with Distinct Eigenvalues
  23. Nov 18, 2009: Strongly Regular Graphs
  24. Nov 20, 2009: Three stories about Strongly Regular Graphs
  25. Dec 2, 2009: Planar Graphs, part 1
  26. Dec 4, 2009: Planar Graphs 2, the Colin de Verdiere graph parameter

This material is based upon work supported by the National Science Foundation under Grant Nos. 0634957 and 0915487. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).