Time: Tue Thu 11:30-13:00

Location: A201

Instructors :

Homepage:
http://www.tcs.tifr.res.in/~prahladh/teaching/2017-18/spectral/

Course Calendar (Click here to subcribe to the calendar (ical format))

- Problem Set 1 [pdf (out: 7 Feb, due: 21 Feb)]

29 Jan |
1. IntroductionAdministrivia; Course Contents; Examples of simple graphs, Matrices: Adjacency, Transition, Laplacian; Spectral Theorem; Rayleigh Coefficient; Hoffman Bound and application to Erdos-Ko-Rado Ref:[HS (Spectral Methods module), Spi (Lecture 1 (Sec 1.4-1.6), Lecture 6 (Sec 6.1-6.3)), Jupyter Notebook (source code] |

31 Jan |
2. Basic Spectral Theory and some applicationsCourant Fischer Theorem; Eigenvalues of Adjacency Matrix; Wilf-bound for chromatic number; Laplacian examples: complete graph, line graph, cycle Ref: [HS (Spectral Methods module), Spi (Lecture 2 (Sec 2.1-2.2), Lecture 3 (Sec 3.1-3.4, 3.7))] |

5 Feb |
3. Spectrum of some fundamental graphsSpectrum of cycles, paths, product-graphs, grid-graphs, Boolean hypercube, Cayley graphs; Edge-expansion, conductance of graph Ref: [HS (Spectral Methods module), Spi (Lecture 3 (Sec 3.5, 3.7, 3.8))] |

7 Feb |
4. Cheeger Inequalities (Part I)Generalized Laplacian, eigenspectrum of random walk matrix, Cheeger Inequalities, Proof of easy direction Ref: [HS (Spectral Methods module), Spi (Lecture 11)] |

12 Feb |
5. Cheeger Inequalities (part II)Proof of hard direction, Fieldler's spectral partitioning algorithm, Trevisan's analysis, tight examples. Ref: [notes, HS (Spectral Methods module), Spi (Lecture 11), Luca Trevisan's blog "In Theory" (blogpost 1, blogpost 2) ] |

14 Feb |
6. Lovasz Theta Function and Applications
(Guest Lecturer: Yuval
Filmus)Lovasz Theta function, Hoffman and Schrijver bound, Traffic light puzzle, Applications Ref: [notes, Fil (Chapter 3)] |

20 Feb |
7. Triangle-Intersecting Families of Graphs
(Guest Lecturer: Yuval
Filmus)Ref: [Fil (Chapter 4)] |

- (6-7 lectures) Application to Combinatorics: Hoffman
bound, EKR theorems, Delsarte's LP bound for codes

- (6 lectures) Expansion: Ramanujan graphs, matrix concentration,
expander graph
constructions, zig-zag product, limits to expansion, small-set
expansion, high-dimensional expansion

- (2-3 lectures) Special graphs: Kneser, Johnson, Grassman graphs

- (2-3 lectures) Sparsifiers
- (2 lectures) Other topics: planted clique, random 3SAT

The links below point to the actual location of papers at the author's homepages or other electronic repositories and the papers are not reposted locally.

**[Fil]**Yuval Filmus, Spectral methods in extremal combinatorics, PhD thesis, University of Toronto, 2013.**[HS]**A module on Spectral Methods in the course on Toolkit for Theoretical Computer Science (offered by Prahladh Harsha and Piyush Srivastava at TIFR, Monsoon 2018: [pdf]**[Spi]**A course on Spectral Methods offered (by Dan Spielman) at Yale University: CPSC 662 / AMTH 561 : Spectral Graph Theory, Fall 2018.

Students taking the course for credit will be expected to:

- Attend lectures
- Do problem sets (approx 1 pset every 2.5 weeks)
- Give a presentation

This page has been accessed at least times since Jan 26, 2019.

Prahladh Harsha |