Course details
A specialist MAGIC course
Semester
 Autumn 2020
 Monday, October 5th to Friday, December 11th
Hours
 Live lecture hours
 10
 Recorded lecture hours
 0
 Total advised study hours
 40
Timetable
 Mondays
 13:05  13:55 (UK)
Description
Combinatorial graphs and networks appear in many theoretical and practical contexts.
It is beneficial for every working mathematician and theoretical computer scientist to have a good familiarity with these concepts.
A very active research area is spectral graph theory, where graphs and their properties are studied via the eigenvalues of their associated adjacency matrices.
This topic is particularly appealing since it needs very little background knowledge and leads efficiently to many beautiful and deep observations and results.
We will cover various useful aspects of general interest with a geometric viewpoint, amongst them: variational characterisation of eigenvalues, Cheeger isoperimetric constants or expansion rates and inequalities between them and eigenvalues, leading to the timely topics of expander graphs, spectral clustering, construction of codes, Ramanujan graphs, and Cayley graphs as geometric representations of discrete groups.
We will discuss fundamental connections between eigenvalues and dynamics like mixing properties of random walks and electrical networks.
We will study eigenvalue relations under graph constructions like coverings, zigzag products, and line graphs, and we will also investigate the interplay between eigenvalues and specific discrete curvature notions (like one based on optimal transport).
In summary, the course provides a variety of interesting tools which can be used to study graphs and networks both from a geometric and an algebraic viewpoint via eigenvalues.
It is beneficial for every working mathematician and theoretical computer scientist to have a good familiarity with these concepts.
A very active research area is spectral graph theory, where graphs and their properties are studied via the eigenvalues of their associated adjacency matrices.
This topic is particularly appealing since it needs very little background knowledge and leads efficiently to many beautiful and deep observations and results.
We will cover various useful aspects of general interest with a geometric viewpoint, amongst them: variational characterisation of eigenvalues, Cheeger isoperimetric constants or expansion rates and inequalities between them and eigenvalues, leading to the timely topics of expander graphs, spectral clustering, construction of codes, Ramanujan graphs, and Cayley graphs as geometric representations of discrete groups.
We will discuss fundamental connections between eigenvalues and dynamics like mixing properties of random walks and electrical networks.
We will study eigenvalue relations under graph constructions like coverings, zigzag products, and line graphs, and we will also investigate the interplay between eigenvalues and specific discrete curvature notions (like one based on optimal transport).
In summary, the course provides a variety of interesting tools which can be used to study graphs and networks both from a geometric and an algebraic viewpoint via eigenvalues.
Prerequisites
The course will be self contained.
Only basic knowledge in linear algebra (linear maps, symmetric matrices, eigenvalues), graph theory (vertices and edges of graphs, graph automorphisms), algebra (discrete groups and generators, symmetry groups), and probability theory (discrete probability spaces) is needed.
Only basic knowledge in linear algebra (linear maps, symmetric matrices, eigenvalues), graph theory (vertices and edges of graphs, graph automorphisms), algebra (discrete groups and generators, symmetry groups), and probability theory (discrete probability spaces) is needed.
Syllabus
Lecture 1: The Adjacency Matrix (simple graphs, adjacency matrices, (adjacency) eigenvalues and spectrum)
Lecture 2: More about the adjacency matrix (induced subgraphs, interlacing, diameter, line graphs)
Lecture 3: Laplacian and Cheeger constant (nonnormalized Laplacian, variational characterisation of eigenvalues, Rayleigh Quotients, Cheeger (isoperimetric) constants, expanders, Cheeger inequality)
Lecture 4: Cheeger Inequality and Spectral Clustering (Cheeger Inequality and Spectral Geometry, CoArea Formula, Spectral Clustering and kmeans algorithm, higher order Cheeger constants and inequalities)
Lecture 5: Ramanujan graphs and LubotzkyPhillipsSarnak Construction (AlonBoppana, Ramanujan Graphs, Cayley Graphs, LubotzkyPhillipsSarnak Construction)
Lecture 6: Lifts, signatures, and the BiluLinial Conjecture (Lifts and covering maps, signatures and associated lifts and signed adjacency matrices, switching equivalence and balanced signatures, old and new eigenvalues of a lift, matching polynomials, common interlacings)
Lecture 7: Logarithmic diameter of expanders, random walks, and the Dirichlet problem (upper diameter estimate for graphs with positive Cheeger constants, application to abelian Cayley graphs, Expander Mixing Lemma, random walks and transition probabilities, Random Walk Laplacian, harmonicity, simple random walks, Maximum Principle, Dirichlet Energy)
Lecture 8: Random walks and electric networks (escape probabilities, electrical networks, voltages, currents, resistances, conductances, energy dissipation, Kirchhoff cycle rule (KCR), Kirchhoff vertex rule (KVR), effective resistance, simple random walk, stationary distribution, mixing rate)
Lecture 9: Zigzag Products and asymptotically good error correcting codes (Replacement and Zigzag product, codewords and binary codes, Hamming distance, Hamming balls, minimal (relative) distance, rate, asymptotically good codes, linear codes, redundency, GilbertVarshamov and sphere packing bounds, graph code)
Lecture 10: Ollivier Riccicurvature on graphs (Background information from Riemannian Geometry, (optimal) transport plans, costs, Wasserstein distance, Duality, (otpimal) Kantorovich potentials, Ollivier Riccicurvature, Discrete BonnetMyers Theorem, Discrete Lichnerowicz Theorem)
Lecturer

Professor Norbert Peyerimhoff
 University
 Durham University
Bibliography
Follow the link for a book to take you to the relevant Google Book Search page
You may be able to preview the book there and see links to places where you can buy the book. There is also link marked 'Find this book in a library'  this sometimes works well, but not always  you will need to enter your location, but it will be saved after you do that for the first time.
 Algebraic Graph Theory (Norman Biggs, book)
 Spectra of Graphs (Andries E. Brouwer and Willem H. Haemers, )
 Expander Families and Cayley Graphs  A Beginner's guide (Mike Krebs and Anthony Shaheen, )
 Random Walks and Electric Networks (Peter G. Doyle and J. Laurie Snell, )
 Spectral Graph Theory (Fan R. K. Chung, )
 Spectral Clustering and Biclustering  Learning Large Graphs and Contingency Tables (Marianna Bolla, )
 Google's PageRank and Beyond  The Science of Search Engine Rankings (Amy N Langville and Carl D Meyer, )
 Introduction to Coding Theory (Ron M Roth, )
 Elementary Number Theory, Group Theory, and Ramanujan Graphs (Giuliana Davidoff, Peter Sarnak, Alain Valette, )
 Discrete Groups, Expanding Graphs and Invariant Measures (Alexander Lubotzky, )
 Expander Graphs And Their Applications (Shlomo Hoory, Nathan Linial, Avi Wigderson, )
 Ramanujan Graphs (M. Ram Murty, )
Assessment
The assessment for this course will be released on Monday 11th January 2021 at 00:00 and is due in before Sunday 24th January 2021 at 23:59.
The assessment for this course will be via a single takehome paper with 2 weeks to complete and submit online. There will be 5 questions and you will need the equivalent of 50% to pass.
Please note that you are not registered for assessment on this course.
Files
Only current consortium members and subscribers have access to these files.
Please log in to view course materials.
Lectures
Please log in to view lecture recordings.