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.
- Combinatorial Theory Seminar