New High Dimensional Expanders from Covers
share
We present a new construction of high dimensional expanders based on covering spaces of simplicial complexes. High dimensional expanders (HDXs) are hypergraph analogues of expander graphs. They have many uses in theoretical computer science, but unfortunately only few constructions are known which have arbitrarily small local spectral expansion. We give a randomized algorithm that takes as input a high dimensional expander X (satisfying some mild assumptions). It outputs a sub-complex Y ⊆ X that is a high dimensional expander and has infinitely many simplicial covers. These covers form new families of bounded-degree high dimensional expanders. The sub-complex Y inherits X's underlying graph and its links are sparsifications of the links of X. When the size of the links of X is O(log |X|), this algorithm can be made deterministic. Our algorithm is based on the groups and generating sets discovered by Lubotzky, Samuels and Vishne (2005), that were used to construct the first discovered high dimensional expanders. We show these groups give rise to many more “randomized” high dimensional expanders. In addition, our techniques also give a random sparsification algorithm for high dimensional expanders, that maintains its local spectral properties. This may be of independent interest.
READ FULL TEXT