Spectral Graph Theory, Fall 2012

Applied Mathematics 561/ Computer Science 662

Instructor: Dan Spielman. Office Hours: Th F 4-5
Teaching Assistant: Roy Lederman. Office Hours: M 1-2, W 10:30 - 11:30, (AKW 112) and by request.

Time: M-W 11:35-12:50, in AKW 200 (51 Prospect Street)

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

Here is the course announcement.

Here are the notes from 2009.

Lecture Notes:

  1. Aug 29, 2012: Course Introduction
    Here are the Matlab files I used in the lecture: lap.m, gplot3.m, yaleShieldBig.mat, and dodec.mat.
  2. Aug 31, 2012: The Laplacian Matrix
  3. Sept 5, 2012: The Adjacency Matrix and the nth Eigenvalue
  4. Sept 10, 2012: Bounding Eigenvalues
  5. Sept 12, 2012: Rings, Paths, and Paley Graphs
  6. Sept 17, 2012: Conductance, the Normalized Laplacian, and Cheeger's Inequality
  7. Sept 19, 2012: Fiedler's Theorems on Nodal Domains
  8. Sept 23, 2012: Effective Resistance and Linear Equations
  9. Sept 25, 2012: Recovering a tree structure.
  10. October 1, 2012: Random walks in graphs.
  11. October 3, 2012: Pseudo-Random Generators from Random Walks on Expanders.
  12. October 8, 2012: Properties of Expanders. For this lecture, I recommend my notes from 2009.
  13. October 10, 2012: Introduction to Combinatorial Coding Theory. For this lecture, I recommend my notes from 2009.
  14. October 15, 2012: Expander Codes. For this lecture, I recommend my notes from 2009.
  15. October 17, 2012: Algebraic Constructions of Graphs.
  16. October 22, 2012: The Simplest Construction of Expanders.
  17. October 31, 2012: Iterative Solvers for Linear Equations.
  18. November 5, 2012: The Conjugate Gradient.
  19. November 7, 2012: Preconditioning.
  20. November 12, 2012: Probability Concentration bounds from Graph Spectra.
  21. November 14, 2012: Eigenvalues of Random Graphs.
  22. November 26, 2012: Sparsifiers of Graphs
  23. November 26, 2012: Linear sized sparsifiers of graphs.
  24. December 3, 2012: Eigenvalues of Planar Graphs
  25. December 5, 2012: Eigenvalue Computation, Planar Graphs, and other Neglected Topics.

This material is based upon work supported by the National Science Foundation under Grant Nos. 0634957, 0915487, and 1111257. 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).