Spectral Graph Theory, Spring 2025

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 2019), (Fall 2018), (Fall 2015), (Fall 2012), (Fall 2009).

Not a lecture: Dan's favorite inequality

Lectures:

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