Uploaded June 2026 | Updated September 2026, 3 weeks ago
Computer Science/Discrete Mathematics Seminar II
Topic: A Probabilistic Construction of Bipartite Ramanujan Graphs
Speaker: Yotam Dikstein
Affiliation: Institute for Advanced Study
Date: June 09, 2026
West Lecture Hall
The first construction of Ramanujan graphs is due to Lubotzky, Phillips, and Sarnak (STOC 1986, Combinatorica 1987). Their construction and analysis were deeply algebraic, and at the time it seemed that only algebraic methods were strong enough to gain this level of control over eigenvalues. However, Marcus, Spielman, and Srivastava gave a breakthrough construction of bipartite Ramanujan graphs of all degrees using elementary probabilistic and analytic tools (Annals of Mathematics 2015).
In this talk, we will survey their construction and understand the principles behind it. In particular, we will introduce random "lifts" of a graph as a way to obtain new Ramanujan graphs from existing ones. We will then reduce the analysis of the second-largest eigenvalue of a random lift to bounding the largest root of a random associated polynomial. Finally, we will explore the core contribution of MSS: a probabilistic existential argument for upper-bounding these roots using the theory of interlacing polynomials and multivariate barrier functions.
I will give a gentle introduction to all the notions above and will not assume any prior knowledge other than basic graph theory.
Computer Science/Discrete Mathematics Seminar II
Topic: A Probabilistic Construction of Bipartite Ramanujan Graphs
Speaker: Yotam Dikstein
Affiliation: Institute for Advanced Study
Date: June 09, 2026
West Lecture Hall
The first construction of Ramanujan graphs is due to Lubotzky, Phillips, and Sarnak (STOC 1986, Combinatorica 1987). Their construction and analysis were deeply algebraic, and at the time it seemed that only algebraic methods were strong enough to gain this level of control over eigenvalues. However, Marcus, Spielman, and Srivastava gave a breakthrough construction of bipartite Ramanujan graphs of all degrees using elementary probabilistic and analytic tools (Annals of Mathematics 2015).
In this talk, we will survey their construction and understand the principles behind it. In particular, we will introduce random "lifts" of a graph as a way to obtain new Ramanujan graphs from existing ones. We will then reduce the analysis of the second-largest eigenvalue of a random lift to bounding the largest root of a random associated polynomial. Finally, we will explore the core contribution of MSS: a probabilistic existential argument for upper-bounding these roots using the theory of interlacing polynomials and multivariate barrier functions.
I will give a gentle introduction to all the notions above and will not assume any prior knowledge other than basic graph theory.
