Back to Ahmad's page

MA431 Spectral Graph Theory, Lent Term 2020/21

Taught by Ahmad Abdi and Neil Olver

Course syllabus

Lecture notes

    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.