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.

Problem Sets:

  1. Sept 9, 2009: Problem Set 1 (Due Sept 23)
    This has 9 problems, so I suggest starting it now
  2. Sept 25, 2009: Problem Set 2 (Due Oct 14)
  3. Oct 16, 2009: Problem Set 3 (Due Nov 4)
  4. Nov 9, 2009: Problem Set 4 (Due Nov 20)
  5. Nov 19, 2009: Problem Set 5 (Due Dec 4)

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