Graphs which are expanders both locally and globally
Michael Chapman
Room 116
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 graphs is presently known. In this talk I discuss a new combinatorial construction of such graphs. I 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 I 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.