New Elementary High Dimensional Edge Expanders using Strong Symmetry
Tali Kaufman, Izhar Oppenheim · arXiv (Cornell University) · 2019
Coboundary and cosystolic expansion are notions of expansion that generalize the Cheeger constant or edge expansion of a graph to higher dimensions. The classical Cheeger inequality implies that for graphs edge expansion is equivalent to spectral expansion. In higher dimensions this is not the case: a simplicial complex can be spectrally expanding but not high dimensional edge-expanding. The phenomenon of high dimensional edge expansion in higher dimensions is much more involved than spectral expansion, and is far from being understood. In particular, the only known bounded degree cosystolic expanders are derived from deep mathematical tools that are far from being elementary! In this work we study high dimensional complexes which are {\em strongly symmetric}. Namely, there is a group that acts transitively on top dimensional cells of the simplicial complex [e.g., for graphs it corresponds to a group that acts transitively on the edges]. Using the strong symmetry, we develop a new machinery to prove high dimensional edge expansion. We then use this machinery to construct a new {\em elementary} family of bounded degree two-dimensional cosystolic expanders. Bounded degree cosystolic expanders play a major role in a recent breakthrough construction of quantum error correcting codes that break the state of the art constructions. Thus, any advancement in their construction, and in particular, an elementary construction of such objects is of a major importance.