Ramanujan Complexes and Bounded Degree Topological Expanders
Authors:
- Tali KaufmanTKTali Kaufman
- David KazhdanDKDavid Kazhdan
- Alexander LubotzkyALAlexander Lubotzky
- 1 October 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 484-493
Abstract
Expander graphs have been a focus of attention in computer science in the last four decades. In recent years a high dimensional theory of expanders is emerging. There are several possible generalizations of the theory of expansion to simplicial complexes, among them stand out coboundary expansion and topological expanders. 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, according to these definitions, exist for d ≥ 2. We present an explicit construction of bounded degree complexes of dimension d = 2 which are high dimensional expanders. More precisely, our main result says that the 2-skeletons of the 3-dimensional Ramanujan complexes are topological expanders. Assuming a conjecture of Serre on the congruence subgroup property, infinitely many of them are also coboundary expanders.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- High dimensional expanders and property testing2014
- Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees2013
- On Multiplicative $\lambda$-Approximations and Some Geometric ApplicationsSIAM Journal on Computing, 2013
- Expander graphs in pure and applied mathematicsBulletin of the American Mathematical Society, 2012
- 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
- Explicit constructions of Ramanujan complexes of typeEuropean Journal of Combinatorics, 2005
- Discrete Groups, Expanding Graphs and Invariant Measures1994
- Le Probleme des Groupes de Congruence Pour SL 2Annals of Mathematics, 1970