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

The theory of linear algebra of symmetric matrices: the Spectral Theorem and the CourantFischer Theorem.

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

Cayley graphs and the Paley graph.

The extreme eigenvalues of the adjacency matrix and the PerronFrobenius theorem.

Cauchy's interlacing theorem

Random walks on graphs

Cheeger's inequality

The power method

Expander graphs  properties, constructions (including ZigZag and the wide replacement product), and applications.

Reingold's SL = L

TaShma's explicit construction of codes close to the GilbertVarshamov bound

Resister networks

The matrixtree theorem

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.
â€‹
Slides
Unit 1. Introduction
Unit 2. Spectral theory of real symmetric matrices
Unit 3. Graph drawing using the Laplacian
Unit 4. The extreme eigenvalues of the adjacency matrix
Unit 5. Cauchy's interlacing theorem
Unit 6. Random walks on graphs
Unit 7. Graph partitioning and Cheeger's inequality
Unit 8. Expander graphs
Unit 9. Explicit constructions of expander graphs
Unit 10. SL = L
Unit 11. Small bias sets
Unit 12. Explicit almost Ramanujan graphs
Unit 13. Spectral graph sparsification
Unit 14. Course summary
Annotated slides
Unit 1. Introduction
Unit 2. Spectral theory of real symmetric matrices
Unit 3. Graph drawing using the Laplacian
Unit 4. The extreme eigenvalues of the adjacency matrix
Unit 5. Cauchy's interlacing theorem
Unit 6. Random walks on graphs
Unit 7. Graph partitioning and Cheeger's inequality
Unit 8. Expander graphs
Unit 9. Explicit constructions of expander graphs
Unit 10. SL = L
Unit 11. Small bias sets
Unit 12. Explicit almost Ramanujan graphs
Unit 13. Spectral graph sparsification
Recitations
The recitation notes may contain Hebrew letters
Recitation 1  working through examples
Recitation 2  operations on graphs and the resulted spectrum
Recitation 3  group theory and characters recall; Cayley graphs
Recitation 5  Hoffman's lower bound on the chromatic number
Recitation 6  Spectrum of random graphs
Recitation 7  The power method
Recitation 8  Cont last time; The GaberGalil expander
Recitation 9  The GaberGalil construction continued
Recitation 10  Resister networks
When and where
The lectures take "place" on Tuesday 9:0012: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 takehome 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 GodsilRoyle book are available, for free, online. You won't need a copy of the latter, so no worries.

Salil Vadhan chapter on expander graphs from his Pseudorandomness monograph.

AlonGoldreichHastadPeralta's construction of smallbias sets

A twopart video talk by Amnon TaShma on his smallbias sets construction (part 1, part 2).