Isoperimetric inequalities in simplicial complexes

DOI10.1007/s00493-014-3002-xzbMath1389.05174arXiv1207.0638OpenAlexW3105794348MaRDI QIDQ2400106

Ron Rosenthal, Ori Parzanchevski, Ran J. Tessler

Publication date: 25 August 2017

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.0638

zbMATH Keywords

Hodge decompositionCheeger-type inequalityisoperimetric inequalitiesspectral gapCheeger constantBetti numberhigh dimensional Laplacian\(d\)-dimensional simplicial complexesgeometric overlaphigh-dimensional expander mixing lemmarandom Linial-m Meshulam complexes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) General topics in linear spectral theory for PDEs (35P05) Simplicial sets and complexes in algebraic topology (55U10) Combinatorial aspects of simplicial complexes (05E45)

Related Items

Kazdan-Warner equation on infinite graphs, Inverse expander mixing for hypergraphs, A Cheeger-Buser-type inequality on CW complexes, Spectrum and combinatorics of two-dimensional Ramanujan complexes, A Cheeger-type inequality on simplicial complexes, Algebraic and combinatorial expansion in random simplicial complexes, What Are Higher-Order Networks?, Graphical designs and extremal combinatorics, Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian, Bounded degree cosystolic expanders of every dimension, Mixing in High-Dimensional Expanders, 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, High dimensional Hoffman bound and applications in extremal combinatorics, Simplicial complexes: Spectrum, homology and random walks, Ramanujan complexes and high dimensional expanders, The geometry of synchronization problems and learning group actions, Spectral gap of the discrete Laplacian on triangulations, Expansion of random graphs: new proofs, new results, On eigenvalues of random complexes, On the chromatic number of a simplicial complex, Kirchhoff index of simplicial networks, Toward a spectral theory of cellular sheaves, Random walks on simplicial complexes and harmonics, The theta number of simplicial complexes, Hypergraph expanders from Cayley graphs, Random Steiner systems and bounded degree coboundary expanders of every dimension

Cites Work

• Unnamed Item
• Unnamed Item
• A Cheeger-type inequality on simplicial complexes
• On eigenvalues of random complexes
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• On Gromov's method of selecting heavily covered points
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Sparsest cuts and bottlenecks in graphs
• Ramanujan complexes of type \(\widetilde A_d\)
• Homological connectivity of random 2-complexes
• Lifts, discrepancy and nearly optimal spectral gap
• Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski
• Expanding graphs contain all small trees
• Explicit construction of linear sized tolerant networks
• Ramanujan graphs
• Eigenvalues and expanders
• The complexity of testing whether a graph is a superconcentrator
• On the second eigenvalue of a graph
• A Tverberg-type result on multicolored simplices
• Computing Betti numbers via combinatorial Laplacians
• On the second eigenvalue of hypergraphs
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• p-adic curvature and the cohomology of discrete subgroups of p-adic groups
• Eigenvalues and homology of flag complexes and vector representations of graphs
• Harmonic functions and boundary value problems on a chain complex
• On Multiplicative $\lambda$-Approximations and Some Geometric Applications
• Higher dimensional discrete Cheeger inequalities
• Expander graphs in pure and applied mathematics
• Overlap properties of geometric expanders
• Explicit Concentrators from Generalized N-Gons
• Expander graphs and their applications
• A proof of Alon’s second eigenvalue conjecture and related problems
• Homological connectivity of random k -dimensional complexes
• Simplicial matrix-tree theorems
• A note on the isoperimetric constant
• Finite-Difference Approach to the Hodge Theory of Harmonic Forms
• Combinatorial Laplacians of matroid complexes
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• COBOUNDARY EXPANDERS