Date
Tue, 14 May 2019
Time
14:30 - 15:30
Location
L6
Speaker
Michael Chapman

Further Information

Expander graphs play a key role in modern mathematics and computer science. Random d-regular graphs are good expanders. Recent developments in PCP theory require families of graphs that are expanders both globally and locally. The meaning of “globally" is the usual one of expansion in graphs, and locally means that for every vertex the subgraph induced by its neighbors is also an expander graph. These requirements are significantly harder to satisfy and no good random model for such (bounded degree) graphs is presently known. In this talk we discuss two new combinatorial constructions of such graphs. We also say something about the limitations of such constructions and provide an Alon-Bopanna type bound for the (global) spectral gap of such a graph. In addition we discuss other notions of high dimensional expansion that our constructions do and do not satisfy, such as coboundary expansion, geometric overlap and mixing of the edge-triangle-edge random walk. This is a joint work with Nati Linial and Yuval Peled.
 

Please contact us with feedback and comments about this page. Last updated on 04 Apr 2022 15:24.