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

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.