Higher-dimensional Expansion of Random Geometric Complexes
summary
Shows that triangles in a random geometric graph on the D-sphere produce a sparse 2D spectral expander: pick C log n dimensions and edge probability p = n^{-(1−ε)} so average degree ≈ degree n^ε, then with high probability every vertex link has spectral gap at most local spectral gap 1/2−δ, and the trickling-down argument yields global expansion. Proof uses random restrictions of the continuous spherical graph, analyzes random-walk contraction via coupling to Brownian motion, and succeeds for arbitrarily small polynomial degree.
AI-written summary · about
chapters (9)
- 0:00Introduction to session
- 1:11Graph expansion basics
- 5:252D spectral expansion
- 10:32Trickling down theorem
- 12:56Existing sparse constructions
- 22:22Random geometric graphs
- 34:00Proof strategy
- 45:44Analyzing local links
- 56:58Future research directions
related talks
57mHigh Dimensional Geometry and Concentration I
01h 03mHigh Dimensional Geometry and Concentration II
49mRecent Advances in Counting Sparse Graphs
46mRandom Walks on Simplicial Complexes and Isoperimetric Inequalities
49mExtremal Cuts of Sparse Random Graphs
01h 03mMathematical connections of some local-to-global expressivity results over geometric graphs and...
45mRandom Walks on Directed Graphs
01h 34mAlgorithmic High-Dimensional Geometry I