High Dimensional Expanders and Sparsifications of the Johnson Graph

High dimensional expanders are an exciting generalization of expander graphs to hypergraphs and other set systems.  Loosely speaking, high dimensional expanders are sparse approximation to the complete hypergraph.  In this talk, we’ll give a gentle introduction to these objects, and see how they arise naturally when analyzing various random walks on hypergraphs.  Finally, we will see some easy applications from the definition: including an algorithm for apprixmate sampling of matroid bases.



Institute for Advanced Study