Mixing in high-dimensional expanders

Abstract

We prove a generalization of the Expander Mixing Lemma for arbitrary (finite) simplicial complexes. The original lemma states that concentration of the Laplace spectrum of a graph implies combinatorial expansion (which is also referred to as mixing, or quasi-randomness). Recently, an analogue of this Lemma was proved for simplicial complexes of arbitrary dimension, provided that the skeleton of the complex is complete. More precisely, it was shown that a concentrated spectrum of the simplicial Hodge Laplacian implies a similar type of expansion as in graphs. In this paper we remove the assumption of a complete skeleton, showing that concentration of the Laplace spectra in all dimensions implies combinatorial expansion in any complex. As applications we show that spectral concentration implies Gromov's geometric overlap property, and can be used to bound the chromatic number of a complex.

References in corpus (4)

• Simplicial complexes: spectrum, homology and random walks
• Expansion of Random Graphs: New Proofs, New Results
• Isoperimetric Inequalities in Simplicial Complexes
• On the chromatic number of a simplicial complex

Cited by in corpus (12)

• Networks beyond pairwise interactions: structure and dynamics
• Simplicial complexes: spectrum, homology and random walks
• Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
• The Ramanujan Property for Simplicial Complexes
• Deterministic tensor completion with hypergraph expanders
• Spectrum and combinatorics of two-dimensional Ramanujan complexes
• Local spectral expansion approach to high dimensional expanders
• Simplicial branching random walks and their applications
• Hypergraph expanders of all uniformities from Cayley graphs
• Free flags over local rings and powering of high dimensional expanders
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• Highlights from "The Ramanujan Property for Simplicial Complexes" [arXiv:1605.02664]