Mixing in high-dimensional expanders
From MaRDI portal
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.
Recommendations
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- A proof of Alon’s second eigenvalue conjecture and related problems
- A Tverberg-type result on multicolored simplices
- Combinatorial Laplacians of matroid complexes
- Computing Betti numbers via combinatorial Laplacians
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- Eigenvalues and expanders
- Eigenvalues and homology of flag complexes and vector representations of graphs
- Expanding graphs contain all small trees
- Expansion of random graphs: new proofs, new results
- Explicit Concentrators from Generalized N-Gons
- Explicit construction of a Ramanujan \((n_1,n_2,\dots,n_{d-1})\)-regular hypergraph
- Explicit construction of linear sized tolerant networks
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Finite-Difference Approach to the Hodge Theory of Harmonic Forms
- Harmonic functions and boundary value problems on a chain complex
- Higher Dimensional Cheeger Inequalities
- Homological connectivity of random 2-complexes
- scientific article; zbMATH DE number 952084 (Why is no real title available?)
- scientific article; zbMATH DE number 3349875 (Why is no real title available?)
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Inverse expander mixing for hypergraphs
- Isoperimetric inequalities in simplicial complexes
- Lifts, discrepancy and nearly optimal spectral gap
- On Gromov's method of selecting heavily covered points
- On the chromatic number of a simplicial complex
- Overlap properties of geometric expanders
- p-adic curvature and the cohomology of discrete subgroups of p-adic groups
- Ramanujan complexes of type \(\widetilde A_d\)
- Ramanujan geometries of type \(\tilde A_{n}\)
- Ramanujan graphs
- Ramanujan hypergraphs
- Random walks on simplicial complexes and harmonics
- Simplicial complexes: spectrum, homology and random walks
- Simplicial matrix-tree theorems
- Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
- Spectra of combinatorial Laplace operators on simplicial complexes
- Spectral sparsification of graphs
- Spectrum and combinatorics of two-dimensional Ramanujan complexes
Cited in
(16)- Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
- Local spectral expansion approach to high dimensional expanders. II: Mixing and geometrical overlapping
- Toward a spectral theory of cellular sheaves
- Hypergraph expanders from Cayley graphs
- Random Steiner systems and bounded degree coboundary expanders of every dimension
- Spectrum and combinatorics of two-dimensional Ramanujan complexes
- High dimensional Hoffman bound and applications in extremal combinatorics
- Inverse expander mixing for hypergraphs
- MIXING IN THE ABSENCE OF THE SHRINKING TARGET PROPERTY
- Mixing properties and the chromatic number of Ramanujan complexes
- Ramanujan complexes and high dimensional expanders
- High order random walks: beyond spectral gap
- Deterministic tensor completion with hypergraph expanders
- Algebraic and combinatorial expansion in random simplicial complexes
- Simplicial branching random walks
- Networks beyond pairwise interactions: structure and dynamics
This page was built for publication: Mixing in high-dimensional expanders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366971)
