Isoperimetric inequalities for Ramanujan complexes and topological expanders

DOI10.1007/S00039-016-0362-YzbMATH Open1339.05075arXiv1409.1397OpenAlexW2962777863MaRDI QIDQ295848FDOQ295848

Tali Kaufman, Alexander Lubotzky, David Kazhdan

Publication date: 14 June 2016

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Abstract: Expander graphs have been intensively studied in the last four decades. In recent years a high dimensional theory of expanders has emerged, and several variants have been studied. Among them stand out coboundary expansion and topological expansion. It is known that for every $d$ there are unbounded degree simplicial complexes of dimension $d$ with these properties. However, a major open problem, formulated by Gromov, is whether bounded degree high dimensional expanders exist for $dgeq2$. We present an explicit construction of bounded degree complexes of dimension $d=2$ which are topological expanders, thus answering Gromov's question in the affirmative. Conditional on a conjecture of Serre on the congruence subgroup property, infinite sub-family of these give also a family of bounded degree coboundary expanders. The main technical tools are new isoperimetric inequalities for Ramanujan Complexes. We prove linear size bounds on $F_2$ systolic invariants of these complexes, which seem to be the first linear $F_2$ systolic bounds. The expansion results are deduced from these isoperimetric inequalities.

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

zbMATH Keywords

expander graphsisoperimetric inequalities for Ramanujan complexes

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The number of triangles covering the center of an \(n\)-set
• A generalization of Caratheodory's theorem
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Expansion of building-like complexes
• 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
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• Homological connectivity of random 2-complexes
• Le problème des groupes de congruence pour \(SL_2\)
• p-adic curvature and the cohomology of discrete subgroups of p-adic groups
• A family of \(\widetilde A_n\)-groups
• Computation of the metaplectic kernel
• The congruence subgroup problem.
• On Expansion and Topological Overlap
• Overlap properties of geometric expanders
• Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds
• Mixing Properties and the Chromatic Number of Ramanujan Complexes
• On Cayley Graphs, Surface Codes, and the Limits of Homological Coding for Quantum Error Correction
• Bounded degree cosystolic expanders of every dimension
• Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).
• Valuation-like maps and the congruence subgroup property
• Ramanujan complexes of type \(\widetilde A_d\)

Cited In (22)

• Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders
• Expansion of building-like complexes
• Random Steiner systems and bounded degree coboundary expanders of every dimension
• Ramanujan complexes and high dimensional expanders
• Random Latin squares and 2-dimensional expanders
• Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes
• Bounded degree cosystolic expanders of every dimension
• Local and global expansion in random geometric graphs
• The theta number of simplicial complexes
• Large simple \(d\)-cycles in simplicial complexes
• Property testing and expansion in cubical complexes
• Nowhere to go but high: a perspective on high-dimensional expanders
• On expansion and topological overlap
• Simplicial branching random walks
• Good quantum LDPC codes with linear time decoders
• Title not available (Why is that?)
• Hypergraph expanders from Cayley graphs
• An elementary exposition of topological overlap in the plane
• Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian
• Boolean function analysis on high-dimensional expanders
• Infinite series of quaternionic 1-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes
• Random walks on Ramanujan complexes and digraphs

This page was built for publication: Isoperimetric inequalities for Ramanujan complexes and topological expanders

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