# COL863: Special Topics in Theoretical Computer Science

Topic: Spectral Graph Theory

# II semester: 2017-18

# Amitabha Bagchi

**Class Timings:** Mon Thu 3:30PM-5PM.

**Room:** Bharti 106.

### Topics

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.

### Texts

- [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.

**Note**: We will basically follow the presentation in [Spielman2015].

### Other links

- 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.

### Refresher texts

- [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.

### Problem sets

- Linear Algebra refresher problem set. Download here. Due at the beginning of class,
**3:30PM, 11 January 2018**.

### Evaluation

TBA

Amitabha
Bagchi