Class materials

Num. Topic Date
1 Introduction, linear algebra review29/10/15
2 Isomorphism, properties of co-spectral graphs, diameter5/11/15
3 Second eigenvalue and connectivity, eigenvalues of basic graphs12/11/15
4 Courant-Fischer, graph inequalities19/11/15
5 Bounds on the Laplacian second eigenvalue, Perron-Forbenius, Wilfe theorem26/11/15
6 Hoffman bound on the chromatic number, the friendship theorem03/12/15
7 Isoperimetric number, Cheeger's inequality (easy direction)10/12/15
8 Cheeger's inequality (hard direction)17/12/15
9 Expander graphs, spectral gap, expander mixing lemma 24/12/15
10 Introduction to error-correcting codes (missing-lemma)31/12/15
11 Expander codes07/01/16
12 Expanders as pseudo-random generators14/01/16
13 Expanders as pseudo-random generators, part 221/01/16