LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
A Probabilistic Construction of Bipartite Ramanujan Graphs
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

A Probabilistic Construction of Bipartite Ramanujan Graphs

101 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 148 Computer Science lectures
Runtime1 h 41 m
Compared with Computer ScienceLonger than 88%
Source channelInstitute for Advanced Study (YouTube)