Spectral Graph Theory

Fall 2020/21

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.

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.

Grading

We expect to hand out about 5 problem sets throughout the semester that will account for half the grade. Submissions are in pairs. A take-home exam, submitted individually, of course, will determine the remaining part of the grade.

Resources

We will not follow any particular text but below are resources which we will use. All but for the Godsil-Royle book are available, for free, online. You won't need a copy of the latter, so no worries.