Topics seminar in spectral graph theory
Ramanujan Graphs and Their Relaxations
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.
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.
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.
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.