Student Probability Seminar

Local and global spectral expansion of graphs

Speaker: Yuval Peled, CIMS

Location: Warren Weaver Hall 512

Date: Monday, April 1, 2019, 1 p.m.


The emerging theory of High-Dimensional Expansion suggests a number of inherently different notions to generalize graph expansion to simplicial complexes. We will talk about the notion of local spectral expansion and its surprising connection to global expansion and rapid mixing of random walks. This connection plays a key role in a recent breakthough by Anari, Lium Oveis Gharan and Nizant who showed that the base-exchange Markov chain of any matroid is rapidly mixing.