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