COL863: Special Topics in Theoretical Computer Science
Topic: Spectral Graph Theory
II semester: 2017-18
Class Timings: Mon Thu 3:30PM-5PM.
Room: Bharti 106.
Spectral theorem for symmetric matrices, the Laplacian, Rayleigh quotient, Eigenvalues of the Laplacian, Spectral partitioning, Cheeger's inequality, Random walks on graphs, Effective resistance, Pseudo-random generators from random walks, Sparsification.
Note: The list of topics is tentative. We will amend it as we go along based on progress and class interest.
Background required: Linear Algebra, Graph Theory, Probability.
Note: We will basically follow the presentation in [Spielman2015].
- [Spielman2015] Daniel A. Spielman. Lecture notes of Spectral Graph Theory, Fall 2015, Yale University. Available here.
- [Chau2015] Lap Chi Chau. Lecture notes of CS798, Spectral Graph Theory, 2015, University of Waterloo. Available here.
- For a general statement of the Perron-Frobenius theorem with proof, see Chapter 9 of the book Dynamical Systems by Shlomo Sternberg.
The entire book can be downloaded at this link.
- [Trevisan2014] Luca Trevisan. Lecture notes on Expansion, Sparsest Cut, and Spectral Graph Theory, 2014. Available here.
- [LP2016] Arbind K Lal, Sukant Pati. Lecture notes on Linear Algebra, July, 2016, IIT Kanpur. Available here.
- [Diestel2016] Reinhard Diestel. Graph theory, 5ed, 2016, Springer. Available here as an ebook.
- Linear Algebra refresher problem set. Download here. Due at the beginning of class, 3:30PM, 11 January 2018.