## Article Source

# 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.

- 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 and 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.