Isoperimetric Inequalities for Ramanujan Complexes and Topological Expanders
Preprint
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 $d \geq 2$. 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.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Singularities, Expanders and Topology of Maps. Part 2: from Combinatorics to Topology Via Algebraic IsoperimetryGeometric and Functional Analysis, 2010
- Homological connectivity of random k‐dimensional complexesRandom Structures & Algorithms, 2008
- Homological Connectivity Of Random 2-ComplexesCombinatorica, 2006
- Ramanujan complexes of typeà dIsrael Journal of Mathematics, 2005
- The congruence subgroup problemProceedings - Mathematical Sciences, 2004
- Valuation-like maps and the congruence subgroup propertyInventiones Mathematicae, 2001
- A family of à n -groupsIsrael Journal of Mathematics, 1998
- Computation of the metaplectic kernelPublications mathématiques de l'IHÉS, 1996
- Discrete Groups, Expanding Graphs and Invariant Measures1994
- The number of triangles covering the center of an n-setGeometriae Dedicata, 1984