# 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

- Keith Conrad. Linear independence of characters, University of Connecticut, undated. Download 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.

### Refresher texts

### Problem sets

- Minor 4. Read description here. Due on moodle by
**11:55PM, 1 May 2018**.
- Minor 3. Read description here. Due on moodle by
**11:55PM, 11 April 2018**.
- Minor 2. Download here. Latex template available on moodle. Due on moodle by
**11:55AM, 12 March 2018**.
- Minor 1. Download here. Latex template available on moodle. Due on moodle by
**11:55AM, 2 February 2018**.
- Linear Algebra refresher problem set. Download here. Due at the beginning of class,
**3:30PM, 11 January 2018**.

### Evaluation

Refresher problem set 10%. Best 3 out of 4 minors 30% each.

Amitabha
Bagchi