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.