Spectral Graph Theory, Fall 2019

Schedule of Lectures and Assignments
Here is the course syllabus.

Readings will come from this draft of a book. You can find lecture notes from previous years here: (Fall 2018), (Fall 2015), (Fall 2012), (Fall 2009).

Not a lecture: Dan's favorite inequality


  1. Aug 28: Introduction. Review of Graphs and Spectral Theory. Survey of highlights of the course.
    Reading: Chapter 1 and Section 2.1. my notes
    462Lect1.ipynb, 462Lect1.pdf, docec.txt, YALE.jld2.
  2. Aug 30: The Laplacian Matrix and Spectral Graph Drawing. Courant-Fischer.
    Reading: Section 2.2 and Chapter 3. my notes.
  3. Sep 4: The Adjacency Matrix, interlacing, and Perron-Frobenius.
    Reading: Chapter 4. my notes.
    ps1 out.
  4. Sep 9: Eigenvalues and Graph Structure: cuts, partitions, and coloring.
    Reading: Chapter on "Independent Sets and Coloring" (but not Section 4) and Chapter on "Graph Partitioning". (now numbered 18 and 19). my notes.
  5. Sep 11: The Zoo of graphs. Bounding eigenvalues by test vectors.
    Reading: Chapter 6. my notes.
  6. Sep 16: Eigenvalue comparison theorems.
    Reading: Chapter 5. my notes. The Jupyter Notebook.
  7. Sep 18: Eigenvalues of random graphs.
    Reading: Chapter 8. my notes. The Jupyter Notebook.
    ps1 due, ps2 out.
  8. Sep 23: Partitioning in Stochastic Block Models.
    Reading: Chapter 22. my notes. The Jupyter Notebook.
  9. Sep 25: Cheeger's inequality.
    Reading: Chapter 21. my notes.
  10. Sep 30: Random Walks on Graphs
    Reading: Chapter 10. my notes.
  11. Oct 2: Local graph clustering
    ps2 due, ps3 out. my notes.
  12. Oct 7: Spring and resistor networks
    Reading: Chapter 11. my notes.
  13. Oct 9: Elimination and Schur Complements. Effective Resistance.
    Reading: Chapter 12. my notes.
  14. Oct 14: Spring embeddings of planar graphs.
    Reading: Chapter 15. my notes.
  15. Oct 21: Computing Effective Resistance.
    Reading: Chapter 14 and Section 12.3. my notes.
    ps3 due, ps4 out.
  16. Oct 23: Introduction to Expander Graphs
    Reading: Chapter 27. my notes.
  17. Oct 28: PSRGs via Random Walks on Expanders
    Reading: Chapter 31, and maybe Section 4 of Chapter 7. my notes.
  18. Oct 30: Introduction to Coding Theory
    Reading: Chapter 28. my notes.
  19. Nov 4: Expander Codes
    Reading: Chapter 29. my notes.
    ps4 due, ps5 out.
  20. Nov 6: A simple construction of expander graphs
    Reading: Chapter 30. my notes.
  21. Nov 11: Sparsification of graphs by random sampling.
    Reading: Chapter 32. my notes.
  22. Nov 13: Linear-sized sparsifiers of graphs.
    Reading: Chapter 33. my notes.
  23. Nov 18: Iterative Solvers for Linear Equations.
    Reading: Chapter 34. my notes.
    ps5 due, ps6 out.
  24. Nov 20: The Conjugate Gradient
    Reading: Chapter 35. my notes.
  25. Dec 2: Preconditioning by low-stretch spanning trees
    Reading: Chapter 36. my notes.
  26. Dec 4: Nearly-linear time Laplacian solvers.
    Reading: Chapter 37. my notes.
    ps6 due.