
Explicit Lossless Vertex Expanders
Rachel Zhang of MIT presents a construction of the first explicit lossless vertex expanders, graphs in which every small subset of vertices has nearly as many neighbors as sparsity theoretically allows. She contrasts this with the previous state of the art, Ramanujan graphs, whose spectral properties only guarantee small vertex sets about half the possible neighbor count. The talk centers on the role of high dimensional expanders as local-to-global amplifiers that let local expansion properties scale up to the lossless global bound. Delivered as part of the IAS Computer Science and Discrete Mathematics seminar at Simonyi Hall, the talk draws on joint work with Jun-Ting Hsieh, Ting-Chun Lin, Alex Lubotzky, Sidhanth Mohanty, Ryan O'Donnell, and Assaf Reiner. It is a research-level seminar aimed at those familiar with spectral graph theory and expander constructions, walking through the construction's key ideas and the obstacles it overcomes.