STOC Conference 2023 Conference Paper
Local and Global Expansion in Random Geometric Graphs
- Siqi Liu 0005
- Sidhanth Mohanty
- Tselil Schramm
- Elizabeth Yang
Consider a random geometric 2-dimensional simplicial complex X sampled as follows: first, sample n vectors u 1 ,…, u n uniformly at random on S d −1 ; then, for each triple i , j , k ∈ [ n ], add { i , j , k } and all of its subsets to X if and only if ⟨ u i , u j ⟩ ≥ τ, ⟨ u i , u k ⟩ ≥ τ, and ⟨ u j , u k ⟩ ≥ τ. We prove that for every ε > 0, there exists a choice of d = Θ(log n ) and τ = τ(ε, d ) so that with high probability, X is a high-dimensional expander of average degree n ε in which each 1-link has spectral gap bounded away from 1/2.