A Probabilistic Construction of Bipartite Ramanujan Graphs - Yotam Dikstein @videosfromIAS
A Probabilistic Construction of Bipartite Ramanujan Graphs - Yotam Dikstein  @videosfromIAS
Uploaded June 2026 | Updated November 2026, 4 days 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.
A Probabilistic Construction of Bipartite Ramanujan Graphs - Yotam DiksteinOpen AIs Proof of the Closed Geodesics Conjecture - Marco MazzucchelliCritical Intent as a Form of Life - Interview with Fernando BrancoliModeling black holes after merger - Marina De AmicisCritical Intent as a Form of Life - For Didier: Reflections and Memories from Colleagues and FriendsIntersection Homology and Combinatorics - Gil KalaiProbability and Intuition - Peter WinklerStability Theory for Minimal Submanifolds - Richard SchoenUnderstanding the Oracle - Govind MenonHelicity as a Foliated Cobordism Invariant 1 - Sobhan SeyfaddiniThermal Giant Graviton Expansion - Kasia BudzikA staircase for the Gromov width of Finsler co-sphere bundles over 𝑅𝑃2 - Vinicius Ramos
Institute for Advanced Study |

A Probabilistic Construction of Bipartite Ramanujan Graphs - Yotam Dikstein

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER