A Probabilistic Construction of Bipartite Ramanujan Graphs
Presenter
June 9, 2026
Abstract
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.