Article Source

• Title: Daniel Spielman “Miracles of Algebraic Graph Theory”

Miracles of Algebraic Graph Theory

• Speaker: Daniel Spielman, Yale University

gives the AMS-MAA Invited Address “Miracles of Algebraic Graph Theory” on January 18, 2019 at the 2019 Joint Mathematics Meetings (JMM) in Baltimore, MD.

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:

• dodec.txt
• YALE.jld2

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