CPSC 662 / AMTH 561: Spectral Graph Theory

The course description may be found here.

Lectures and Assignments

Note: These plans may change, and I have not yet decided on the content of the last 4 lectures.

  1. Aug. 29: Introduction and course overview. Jupyter Notebook, and an HTML version of that, and files used in the lecture:
  1. Aug. 31: Essential spectral theory, Hall's spectral graph drawing, the Fiedler value. ps1 out
  2. Sept. 5: Some fundamental graphs, bounding eigenvalues by test vectors. 3a. Interlude (Sep 8): Dan's favorite inequality
  3. Sept. 10: Bounding eigenvalues by comparison theorems.
  4. Sept. 12: Cayley graphs.
  5. Sept. 17: High-frequency eigenvalues. Independent sets and graph coloring.
  6. Sept. 19: Low-frequency eigenvalues. Nodal Domains. Jupyter Notebook, and the HTML of the notebook ps1 due, ps2 out
  7. Sept. 24: Testing isomorphism of graphs with distinct eigenvalues. Jupyter Notebook and a PDF file of that notebook
  8. Sept. 26: Testing isomorphism of strongly regular graphs.
  9. Oct. 1: Random walks on graphs.
  10. Oct. 3: Cheeger's inequality. ps 2 due, ps3 out
  11. Oct. 8: Phyiscal metaphors for graphs. Spring & Electrical networks.
  12. Oct 10: Elimination and Schur Complements. Effective Resistance.
  13. Oct 15: More effective resistance
  14. Oct 22: Tutte embeddings of planar graphs.
  15. Oct 24: The Fiedler value of planar graphs. ps 3 due, ps4 out
  16. Oct 29: Properties of expander graphs
  17. Oct 31: An elementary construction of expander graphs
  18. Nov 5: Pseudo-random generators from expander graphs
  19. Nov 7: Andersen's proof of Cheeger's inequality using Lovasz-Simonovits. ps 4 due, ps5 out
  20. Nov 12: Sparsification of graphs by random sampling.
  21. Nov 14: Linear-sized sparsifiers of graphs.
  22. Nov 19: Iterative solvers for linear equations
  23. Nov 21: Preconditioning and Laplacian equations
  24. Dec. 3: Bipartite Ramanujan Graphs. ps5 due
  25. Dec. 5: The matching polynomial of a graph.