(2022). Higher-Dimensional Expansion of Random Geometric Complexes. The Simons Institute for the Theory of Computing. https://old.simons.berkeley.edu/talks/testing-thresholds-high-dimensional-random-geometric-graphs
MLA
Higher-Dimensional Expansion of Random Geometric Complexes. The Simons Institute for the Theory of Computing, Oct. 07, 2022, https://old.simons.berkeley.edu/talks/testing-thresholds-high-dimensional-random-geometric-graphs
BibTex
@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}}
}
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.