Back to Ahmad's page
Lecture 10 (Mar 24) Tutte drawings of planar graphs. Multiplicity of λ2 in planar graphs.
Lecture 9 (Mar 17) The matching polynomial and its roots. Bipartite Ramanujan graphs and their existence.
Lecture 8 (Mar 10) Proof of Cheeger's inequality. Expander graphs. Ramanujan graphs.
Lecture 7 (Mar 3) Random walks and electrical networks. Mixing times and the spectral gap. Cheeger's inequality.
Lecture 6 (Feb 24) Second proof of Kirchhoff's effective resistance theorem, Transfer-Current Theorem, weights as conductances.
Lecture 5 (Feb 17) Cycle space, cut space, projection onto cut space, electrical flows, Kirchhoff's effective resistance theorem.
Lecture 4 (Feb 10) The Shannon capacity of 5-hole, Laplacian matrix and spectrum, the Matrix-Tree theorem, applications, the Laplacian matrix of a weighted graph.
Lecture 3 (Feb 3) Boolean functions and the Sensitivity Conjecture, the Courant-Hilbert-Haemers theorem, quotient matrices, stable sets.
Lecture 2 (Jan 27) Proof of the Perron-Frobenius theorem, Cauchy's interlacing theorem, applications to induced subgraphs, chromatic number, stable sets.
Lecture 1 (Jan 20) Adjacency matrix, graph spectrum, directed walks, cospectral pairs, the Perron-Frobenius theorem.
Lecture 0 Spectral Decomposition Theorem, Courant-Fischer Theorem and Rayleigh Inequalities, PSD matrices, Loewner order. Moore-Penrose pseudoinverse. Exercises.