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 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.
Assignment 5 (due Mar 30, 10am BST)