Mixing in high-dimensional expanders
From MaRDI portal
Publication:5366971
DOI10.1017/S0963548317000116zbMATH Open1371.05329arXiv1310.6477MaRDI QIDQ5366971FDOQ5366971
Authors: Ori Parzanchevski 
Publication date: 10 October 2017
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1310.6477
Recommendations
Simplicial sets and complexes in algebraic topology (55U10) Combinatorial aspects of simplicial complexes (05E45) Spectral theory; eigenvalue problems on manifolds (58C40) Hodge theory in global analysis (58A14)
Cites Work
- Eigenvalues and expanders
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Finite-Difference Approach to the Hodge Theory of Harmonic Forms
- Combinatorial Laplacians of matroid complexes
- Expanding graphs contain all small trees
- Spectral sparsification of graphs
- Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
- On Gromov's method of selecting heavily covered points
- Homological connectivity of random 2-complexes
- Lifts, discrepancy and nearly optimal spectral gap
- Ramanujan graphs
- Explicit construction of linear sized tolerant networks
- Isoperimetric inequalities in simplicial complexes
- p-adic curvature and the cohomology of discrete subgroups of p-adic groups
- Inverse expander mixing for hypergraphs
- Explicit Concentrators from Generalized N-Gons
- Simplicial matrix-tree theorems
- Overlap properties of geometric expanders
- A proof of Alon’s second eigenvalue conjecture and related problems
- Expansion of random graphs: new proofs, new results
- Ramanujan complexes of type \(\widetilde A_d\)
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Title not available (Why is that?)
- Eigenvalues and homology of flag complexes and vector representations of graphs
- Harmonic functions and boundary value problems on a chain complex
- On Laplacians of random complexes
- A Tverberg-type result on multicolored simplices
- Ramanujan geometries of type \(\tilde A_{n}\)
- Ramanujan hypergraphs
- Spectrum and combinatorics of two-dimensional Ramanujan complexes
- Explicit construction of a Ramanujan \((n_1,n_2,\dots,n_{d-1})\)-regular hypergraph
- Simplicial complexes: Spectrum, homology and random walks
- Higher Dimensional Cheeger Inequalities
- Title not available (Why is that?)
- Spectra of combinatorial Laplace operators on simplicial complexes
- Computing Betti numbers via combinatorial Laplacians
- On the chromatic number of a simplicial complex
- Random walks on simplicial complexes and harmonics
Cited In (15)
- Networks beyond pairwise interactions: structure and dynamics
- Random Steiner systems and bounded degree coboundary expanders of every dimension
- Ramanujan complexes and high dimensional expanders
- Inverse expander mixing for hypergraphs
- Algebraic and combinatorial expansion in random simplicial complexes
- Bounded degree cosystolic expanders of every dimension
- Toward a spectral theory of cellular sheaves
- MIXING IN THE ABSENCE OF THE SHRINKING TARGET PROPERTY
- Deterministic Tensor Completion with Hypergraph Expanders
- High dimensional Hoffman bound and applications in extremal combinatorics
- Simplicial branching random walks
- Hypergraph expanders from Cayley graphs
- 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
- Spectrum and combinatorics of two-dimensional Ramanujan complexes
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)
