Topics seminar in spectral graph theory
Ramanujan Graphs and Their Relaxations
Fall 2021/22
About the seminar
Spectral expanders are graphs that have many pseudorandom properties that make them central in theoretical computer science, coding theory and cryptography to name a few. The best spectral expanders are dubbed Ramanujan graphs.
This seminar focuses on Ramanujan graphs and their relaxations - bipartite Ramanujan graphs and near Ramanujan graphs. The seminar is a combination of combinatorics and spectral methods, in particular, the study of the characteristic polynomial associated with a graph. We will also take a detour to spectral sparsification so as to sharpen our understanding of the characteristic polynomial of a graph.
The seminar is for undergraduate students and is ran by Gal Maor and myself. To get a taste of what this seminar is about, I recommend the following talk by Daniel Spielman and / or this one.
It is important to stress that this is a mathematical seminar in nature and I expect it to be quite challenging. Hence, registration is recommended only to those who are interested in the subject and are willing to invest a significant amount of time and energy in understanding this beautiful line of research.
Syllabus
Part 1 - Introduction and motivation
(1) Introduction to spectral graph theory, expanders and Ramanujan graphs (given by the lecturer). The slides I used for this and for the next lecture are:
(2) Introductory continued.
(3) Expander codes (chapters 28.1-28.5, 29 in Spielman). Lecturers: David M and Guy E.
(4) The Alon-Boppana bound (paper; see also Section 5.2 in Hoory-Linial-Wigderson) and eigenvalue interlacing (chapter 4.2-4.4 in Spielman). A nice lecture on extensions of the Alon-Boppana bound for non-regular graphs can be found here. Lecturers: Itamar R and Yoav R.
Part 2 - Expanders
(5) Explicit construction of expanders via the line graph (chapter 30 in Spielman). Lecturers: Lin H and Cohav T.
(6) Spectral sparsifiers (chapter 33 in Spielman). See also a talk by Spielman. Lecturers: Maria N and Tomer M.
(7) Bilu-Linial expanders (paper). Lecturers: Itay C and Kedem Y. Slides.
Part 3 - Ramanujan graphs and their relaxations
(8) Introductory lecture to this part (given by the lecturer). Lecturer: Gil
(9) The expected characteristic polynomial (chapter 42 in Spielman). Lecturers: Ronel L and Yuval S.
(10) Quadrature for the finite free convolution (chapter 43 in Spielman). See also Spielman's talk. For a gentle, though more technical, introduction to free probability and finite free probability check out two (mostly independent) lectures by Adam Marcus: this and that. Lecturer: Gil. Slides.
(11) Half Ramanujan graphs of every size and every degree (chapter 44 in Spielman). Lecturers: Maya F B and Tommy K.
(12) Matching polynomials of graphs (chapter 45 in Spielman). Lecturer: Guy S and Amir K.
(13) Bipartite Ramanujan graphs of every degree (chapter 46 in Spielman). Lecturer: Yoav M and Dvir K.