Back to Ahmad's page

MA431 Spectral Graph Theory, Lent Term 2021/22

Taught by Ahmad Abdi and Neil Olver

Course syllabus


    Mar 25: Lecture 10 notes have been updated.

    Mar 23: Lecture 9 notes have been updated; Sections 21.2-3 are new. We covered some of this during Seminar 9; the rest is for you to read.

    Mar 18: Assignment 5 has been posted. It is due Mar 30 at 10am BST.

    Mar 18: Lecture 9 notes are posted.

    Mar 1: Final project (for PhD students) has been released. Project title is due March 25.

Lecture notes

    Lecture 10 (Mar 25) Multiplicity of λ2 in 3-connected planar graphs, generalised Laplacian, Colin de Verdiere number.

    Lecture 9 (Mar 18) Hard direction of Cheeger's inequality, expander graphs, barycentric embeddings, locally convex embeddings, Tutte drawings.

    Lecture 8 (Mar 11) Mixing time, spectral gap, cut and graph cunductance, easy direction of Cheeger's inequality.

    Lecture 7 (Mar 4) notes, slides for first half: Transfer-Current Theorem, conductance and resistance, Rayleigh monotonicity principle, simple random walks, hitting time, commute time.

    Lecture 6 (Feb 25) notes, slides: Projection onto cut space, electrical flows, electrical potentials, effective resistance, Kirchhoff’s effective resistance theorem and a strengthening.

    Lecture 5 (Feb 18) notes, slides: Matrix-Tree Theorem. Kirchhoff polynomial. Laplacian of weighted graph. Cycle and cut spaces.

    Lecture 4 (Feb 11) Laplacian matrix and its spectrum and rank. Deletion-contraction formula.

    Lecture 3 (Feb 4) Proof of Sensitivity Conjecture. Courant-Hilbert-Haemers Theorem. Equitable partitions. Stability number of graphs.

    Lecture 2 (Jan 28) The Perron-Frobenius Theorem, Cauchy's Interlacing Theorem. Applications to graphs.

    Lecture 1 (Jan 21) Adjacency matrix, graph spectrum, directed walks, cospectral graphs, subharmonic vectors.

    Lecture 0 Spectral Decomposition Theorem, Courant-Fischer Theorem and Rayleigh Inequalities, PSD matrices, Loewner order. Moore-Penrose pseudoinverse.