Bounding the High Order Edge Expansion via High Order Radius
Tali Kaufman, Izhar Oppenheim · arXiv (Cornell University) · 2019
We define the notion of cone radius of a simplicial complex that generalizes the known notion of radius of a graph. We show that for symmetric simplicial complexes, the cone radius can be used to give a lower bound on the coboundary expansion of the complex. The coboundary expansion of a complex is the high order analogue of a Cheeger constant or edge expansion in a graph. We then define the notion of filling constants of a complex and use them to bound the cone radius and therefore the coboundary expansion. Our paper gives the first general criterion for obtaining high order expanders in the geometric sense, i.e., high dimensional expanders that satisfy a generalized notion of edge expansion. We further present simplicial complexes that we conjecture to satisfy our criterion and form new coboundary expanders.