
A Probabilistic Construction of Bipartite Ramanujan Graphs
Yotam Dikstein, speaking at the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar, surveys the Marcus, Spielman, and Srivastava construction of bipartite Ramanujan graphs, published in the Annals of Mathematics in 2015. He contrasts their elementary probabilistic and analytic approach with the original algebraic construction of Lubotzky, Phillips, and Sarnak from 1986. The talk introduces random graph lifts as a method for generating new Ramanujan graphs from existing ones, then shows how bounding the second-largest eigenvalue of such a lift reduces to bounding the largest root of an associated random polynomial. Dikstein walks through the core MSS argument, which uses interlacing polynomials and multivariate barrier functions to give a probabilistic existence proof for these bounds. He pitches the talk as a gentle introduction requiring only basic graph theory, building each concept from the ground up over the full session.