Syllabus

Spectral graph theory is the study of a graph via algebraic properties of matrices associated with the graph, in particular, the corresponding eigenvalues and eigenvectors. In this course we will cover the basics of the field as well as applications to theoretical computer science. In particular, after a short linear algebra refresher, tentatively, we plan on covering

1. The theory of linear algebra of symmetric matrices: the Spectral Theorem and the Courant-Fischer Theorem.

2. Hall's graph drawing using the Laplacian's eigenvectors.

3. Cayley graphs and the Paley graph.

4. The extreme eigenvalues of the adjacency matrix and the Perron-Frobenius theorem.

5. Cauchy's interlacing theorem

6. Random walks on graphs

7. Cheeger's inequality

8. The power method

9. Expander graphs - properties, constructions (including Zig-Zag and the wide replacement product), and applications.

10. Reingold's SL = L

11. Ta-Shma's explicit construction of codes close to the Gilbert-Varshamov bound

12. Resister networks

13. The matrix-tree theorem

14. Spectral sparsification

​

I suggest you'll watch Spielman's talk Miracles of Algebraic Graph Theory to get a sense of what this course is mostly about.

​