# Local and global expansion in random geometric graphs

arXiv: https://arxiv.org/abs/2210.00158 · HTML: https://mlsanity.com/paper/2210.00158/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2022.

## Built on by (most cited first, 2 of 2)

- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [Is Dimensionality a Barrier for Retrieval Models?](https://mlsanity.com/paper/2605.23556/) (2026)

## Abstract (arXiv)

Consider a random geometric 2-dimensional simplicial complex X sampled as follows: first, sample n vectors boldsymbolu1,ldots,boldsymbolun uniformly at random on mathbbSd-1; then, for each triple i,j,k ∈ [n], add i,j,k and all of its subsets to X if and only if langleboldsymbolui,boldsymbolujrangle ≥ τ, langleboldsymbolui,boldsymbolukrangle ≥ τ, and langle boldsymboluj, boldsymbolukrangle ≥ τ. We prove that for every varepsilon > 0, there exists a choice of d = Theta(log n) and τ = τ(varepsilon,d) so that with high probability, X is a high-dimensional expander of average degree n^varepsilon in which each 1-link has spectral gap bounded away from frac12. To our knowledge, this is the first demonstration of a natural distribution over 2-dimensional expanders of arbitrarily small polynomial average degree and spectral link expansion better than frac12. All previously known constructions are algebraic. This distribution also furnishes an example of simplicial complexes for which the trickle-down theorem is nearly tight. En route, we prove general bounds on the spectral expansion of random induced subgraphs of arbitrary vertex transitive graphs, which may be of independent interest. For example, one consequence is an almost-sharp bound on the second eigenvalue of random n-vertex geometric graphs on mathbbSd-1, which was previously unknown for most n,d pairs.