Spectral Graph Theory, Spring 2025

Schedule of Lectures and Assignments
Here is the course syllabus.

Readings will come from this draft of a book.

The Julia code that I use to generate the examples in lecture is in this GitHub repository.

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. my notes
   A pdf of the Jupyter notebook from class.
   
2. Jan 15: The Laplacian Matrix and Spectral Graph Drawing. Courant-Fischer.
   Reading: Section 2.2 and Chapter 3. my notes.
3. Jan 22: Adjacency Matrix eigenvalues, Perron-Frobenius theory, and graph coloring.
   Reading: Chapter 4, but skipping Section 4.3. my notes.
   ps1 out.
4. Jan 24: Eigenvalue Interlacing, Graph Coloring, and Independent Sets.
   Reading: Section 4.3, and chapter on "Independent Sets and Coloring" (but not Section 4). my notes.
5. Jan 27: Eigenvalues and graph partitioning.
   Reading: Chapter on "Graph Partitioning", and sections 4 and 5 of "Nodal Domains" my notes.
6. Jan 29: The Zoo of graphs. Bounding eigenvalues by test vectors.
   Reading: Chapter 5. my notes.
7. Feb 3: Eigenvalue comparison theorems.
   Reading: Chapter 6. my notes.
   ps1 due, ps2 out.
8. Feb 5: Eigenvalues of random graphs.
   Reading: Chapter 8. my notes, and the pdf of the Jupyter Notebook.
Feb 7: Bonus Lecture by Marco Pirazzini on Eigenvalues and Eigenvectors of Cayley Graphs
Reading: Marco's notes.
9. Feb 10: Partitioning in Stochastic Block Models.
   Reading: Chapter 23. my notes, and the pdf of the Jupyter Notebook.
10. Feb 12: Cheeger's inequality.
    Reading: Chapter 21. my notes.
11. Feb 17: Random Walks on Graphs
    Reading: Chapter 10. my notes.
    ps2 due, ps3 out.
12. Feb 19: Spring and resistor networks
    Reading: Chapter 11. my notes.
13. Feb 24: Elimination and Schur Complements. Effective Resistance.
    Reading: Chapter 12. my notes.
14. Feb 26: Spring embeddings of planar graphs.
    Reading: Chapter 15. my notes.
15. Mar 3: Introduction to Expander Graphs
    Reading: Chapter 27. my notes.
    ps3 due, ps4 out.
16. Mar 5: PSRGs via Random Walks on Expanders
    Reading: Chapter 31, and maybe Section 4 of Chapter 7. my notes.
Spring Break!
17. Mar 24: Introduction to Coding Theory
    Reading: Chapter 28. my notes.
18. Mar 26: Expander Codes
    Reading: Chapter 29. my notes.
    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.
22. Apr 9: Iterative Solvers for Linear Equations.
    Reading: Chapter 34.
    ps5 due, ps6 out.
23. Apr 14: The Conjugate Gradient
    Reading: Chapter 35.
24. Apr 16: Preconditioning by low-stretch spanning trees
    Reading: Chapter 36.
25. Apr 21: Nearly-linear time Laplacian solvers.
    Reading: Chapter 37.
26. Apr 23: Developments in Spectral Graph Theory, and other cool related topics.
    ps6 due.