Higher-Dimensional Expansion of Random Geometric Complexes

          @misc{ scivideos_22707,
            doi = {},
            url = {https://old.simons.berkeley.edu/talks/testing-thresholds-high-dimensional-random-geometric-graphs},
            author = {},
            keywords = {},
            language = {en},
            title = {Higher-Dimensional Expansion of Random Geometric Complexes},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2022},
            month = {oct},
            note = {22707 see, \url{https://scivideos.org/simons-institute/22707}}
          }
          

Abstract

A graph is said to be a (1-dimensional) expander if the second eigenvalue of its adjacency matrix is bounded away from 1, or almost-equivalently, if it has no sparse vertex cuts. There are several natural ways to generalize the notion of expansion to hypergraphs/simplicial complexes, but one such way is 2-dimensional spectral expansion, in which the expansion of vertex neighborhoods (remarkably) witnesses global expansion. While 1-dimensional expansion is known to be achieved by, e.g., random regular graphs, very few constructions of sparse 2-dimensional expanders are known, and at present all are algebraic. It is an open question whether sparse 2-dimensional expanders are "abundant" and "natural" or "rare." In this talk, we'll give some evidence towards abundance: we show that the set of triangles in a random geometric graph on a high-dimensional sphere yields an expanding simplicial complex of arbitrarily small polynomial degree.