Bounded degree cosystolic expanders of every dimension

DOI10.1145/2897518.2897543zbMATH Open1376.05095arXiv1510.00839OpenAlexW2255379171MaRDI QIDQ5361817FDOQ5361817

Tali Kaufman, Shai Evra

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, Journal of the American Mathematical Society (Search for Journal in Brave)

Abstract: In this work we present a new local to global criterion for proving a form of high dimensional expansion, which we term cosystolic expansion. Applying this criterion on Ramanujan complexes, yields for every dimension, an infinite family of bounded degree complexes with the topological overlapping property. This answer affirmatively an open question raised by Gromov.

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

Recommendations

• Bounded degree cosystolic expanders of every dimension
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Exposé Bourbaki 1187 : High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others)
• High dimensional expanders and coset geometries
• Random Steiner systems and bounded degree coboundary expanders of every dimension

zbMATH Keywords

high-dimensional expandersRamanujan complexestopological overlappingcosystolic expansioncosystolic expandersinfinite family of bounded degree complexes

Mathematics Subject Classification ID

Simplicial sets and complexes in algebraic topology (55U10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65) Global geometric and topological methods (à la Gromov); differential geometric analysis on metric spaces (53C23) General geometric structures on low-dimensional manifolds (57M50) Relations of low-dimensional topology with graph theory (57M15) Expander graphs (05C48)

Cites Work

• Buildings
• The number of triangles covering the center of an \(n\)-set
• A generalization of Caratheodory's theorem
• Expansion of building-like complexes
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Expander graphs in pure and applied mathematics
• Expander graphs and their applications
• Homological connectivity of random k -dimensional complexes
• Ramanujan complexes and high dimensional expanders
• Random Latin squares and 2-dimensional expanders
• COBOUNDARY EXPANDERS
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• Homological connectivity of random 2-complexes
• Uniform pointwise bounds for matrix coefficients of unitary representations and applications to Kazhdan constants
• Isoperimetric inequalities in simplicial complexes
• p-adic curvature and the cohomology of discrete subgroups of p-adic groups
• Mixing in High-Dimensional Expanders
• Overlap properties of geometric expanders
• Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds
• Mixing Properties and the Chromatic Number of Ramanujan Complexes
• Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).
• Ramanujan complexes of type \(\widetilde A_d\)
• On Laplacians of random complexes
• Finite quotients of Bruhat–Tits buildings as geometric expanders
• Simplicial complexes: Spectrum, homology and random walks
• Higher dimensional discrete Cheeger inequalities
• HIGH DIMENSIONAL EXPANDERS
• On expansion and topological overlap
• Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
• Generalizations of the Kolmogorov-Barzdin embedding estimates
• High Dimensional Random Walks and Colorful Expansion
• Eigenvalue confinement and spectral gap for random simplicial complexes
• Random Steiner systems and bounded degree coboundary expanders of every dimension
• The Need for Structure in Quantum LDPC Codes

Cited In (24)

• Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders
• Phase transitions of structured codes of graphs
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Random Steiner systems and bounded degree coboundary expanders of every dimension
• Expander graphs -- both local and global
• Testing Odd Direct Sums Using High Dimensional Expanders
• Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes
• Bounded degree cosystolic expanders of every dimension
• Exposé Bourbaki 1187 : High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others)
• Local and global expansion in random geometric graphs
• The theta number of simplicial complexes
• High dimensional expanders and coset geometries
• Quantitative null-cobordism
• Nowhere to go but high: a perspective on high-dimensional expanders
• On expansion and topological overlap
• Coboundary expansion for the union of determinantal hypertrees
• High Dimensional Random Walks and Colorful Expansion
• Good quantum LDPC codes with linear time decoders
• Title not available (Why is that?)
• Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion
• Hypergraph expanders from Cayley graphs
• Homological filling functions with coefficients
• Boolean function analysis on high-dimensional expanders
• Random walks on Ramanujan complexes and digraphs

This page was built for publication: Bounded degree cosystolic expanders of every dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361817)