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

Lectures:

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
   Files: 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.