Spectral Graph Theory, Fall 2015

Applied Mathematics 561/ Computer Science 662

Instructor: Dan Spielman. Office Hours: Friday, 3:00 - 4:00

Time: M-W 2:30-3:45. DL 220

Here is the course syllabus.

For alternative treatements of material from this course, I recommend my notes from 2012, 2009, and 2004, as well as the notes from other related courses.

For a sales pitch for the type of material I cover in this course see the notes from my first lecture in 2009.

Lectures:

  1. Sep 2, 2015: Course Introduction . Solutions to exercises are available under "Resources" on ClassesV2.
    Here are the Matlab files I used in the lecture: lap.m, gplot3.m, yaleShieldBig.mat, and dodec.mat.

  2. Sep 4, 2015: The Laplacian Matrix and Spectral Graph Drawing. Solutions to exercises are available under "Resources" on ClassesV2. (PS 1 out)

  3. Sept 9, 2015: The Adjacency Matrix and Graph Coloring

  4. Sept 14, 2015: Bounding Eigenvalues

  5. Sept 16, 2015: Rings, Paths, and Cayley Graphs

  6. Sept 21, 2015: Conductance, the Normalized Laplacian, and Cheeger's Inequality. (PS 1 due, PS 2 out)

  7. Sept 23, 2015: Spring and resistor networks

  8. Sept 28, 2015: Effective resistance and Schur complements

  9. Sept 30, 2015: How to draw a planar graph.

  10. Oct 5, 2015: Random walks and diffusion. (PS 2 due, PS 3 out)

  11. Oct 7, 2015: Pseudo-random generators from random walks on expanders.

  12. Oct 12, 2015: Iterative Solvers for Linear Equations.

  13. Oct 14, 2015: The Conjugate Gradient. This will be a guest lecture by Sushant Sachdeva. I have posted my old notes on the topic. I also recommend his monograph Faster Algorithms via Approximation Theory.

  14. Oct 19, 2015: Preconditioning and low stretch spanning trees. (PS 3 due)

  15. Oct 26, 2015: Properties of expander graphs. (PS 4 out)

  16. Oct 28, 2015: A simple construction of expander graphs.

  17. Nov 2, 2015: Sparsification by effective resistance random sampling.

  18. Nov 4, 2015: Linear sized sparsifiers.

  19. Nov 9, 2015: Fast Laplacian solvers by sparsification.

  20. Nov 11, 2015: The spectral gap of planar graphs. (PS 4 due, PS 5 out)

  21. Nov 16, 2015: Partitioning in block models.

  22. Nov 18, 2015: Expected characteristic polynomials.

  23. Nov 30, 2015: Quadrature for the finite free convolution.

  24. Dec 2, 2015: Interlacing polynomials and Ramanujan Graphs.

  25. Dec 7, 2015: The matching polynomial of a graph. (PS 5 due)

  26. Dec 9, 2015: Ramanujan covers of graphs.

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).