top of page

Spectral Graph Theory

Fall 2020/21

Final Exam

The final exam can be downloaded from here. (updated on Feb 2nd, 12:30).

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.

Annotated slides

Unit 1. Introduction

Unit 5. Cauchy's interlacing theorem

Unit 6. Random walks on graphs

Unit 8. Expander graphs

Unit 10. SL = L

Unit 11. Small bias sets

Unit 12. Explicit almost Ramanujan graphs

Unit 13. Spectral graph sparsification

When and where

The lectures take "place" on Tuesday 9:00-12:00 via this Zoom link. The recitation, by Shir, is in the following hour.

Prerequisite

The technical prerequisite is very mild: a first course on linear algebra and the first course on algorithms.  However, I stress that this is an advanced course of mathematical nature, and so mathematical maturity is essential to follow the course successfully.