Siqi Liu, DIMACS

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 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 local expansion of vertex links/neighborhoods witnesses global expansion. While 1-dimensional expansion is known to be achieved by, e.g., random regular graphs, very few examples of sparse 2-dimensional expanders are known, and at present all are algebraic. It is an open question whether sparse 2-dimensional expanders are natural and abundant.

In this talk, we 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.

Consider a random geometric 2-dimensional simplicial complex X sampled as follows: first, sample n vectors u_1, …, u_n uniformly at random on the d-dimensional unit sphere; 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⟩ ≥ t,⟨u_i, u_k⟩≥ t, and ⟨u_j, u_k⟩ ≥ t. We prove that for every ε > 0, there exists a choice of d = Θ(logn) and t = t(ε,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.
 

Based on joint work with Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang.

See: https://theory.cs.rutgers.edu/theory_seminar