Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-134 | 24th July 2018 14:11

Cosystolic Expanders over any Abelian Group


Authors: Tali Kaufman, David Mass
Publication: 30th July 2018 15:29
Downloads: 898


In this work we show a general reduction from high dimensional complexes to their links based on the spectral properties of the links. We use this reduction to show that if a certain property is testable in the links, then it is also testable in the complex. In particular, we show that expansion of the links of a complex over any abelian group implies that the complex is an expander \emph{over the same group}.

Previous works studied the expansion properties of complexes from their links, but their proofs were tailored for the field $\mathbb{F}_2$. They showed that the combination of spectral and topological properties of the links of a complex implies its expansion over the field $\mathbb{F}_2$. We show here a general reduction based \emph{only} on the spectral properties of the links.

We then show that all the links of Ramanujan complexes (which are called spherical buildings) are expanders over any abelian group. For this we generalize the result of~\cite{LMM16}, who showed that spherical buildings are coboundary expanders over $\mathbb{F}_2$. Combined with our reduction, this implies the existence of bounded degree cosystolic expanders over any abelian group.

ISSN 1433-8092 | Imprint