TY - GEN

T1 - Bounded degree cosystolic expanders of every dimension

AU - Evra, Shai

AU - Kaufman, Tali

N1 - Publisher Copyright:
© 2016 ACM.

PY - 2016/6/19

Y1 - 2016/6/19

N2 - In recent years a high dimensional theory of expanders has emerged. The notion of combinatorial expansion of graphs (i.e. the Cheeger constant of a graph) has seen two generalizations to high dimensional simplicial complexes. One generalization, known as coboundary expansion, is due to Linial and Meshulem; the other, which we term here cosystolic expansion, is due to Gromov, who showed that cosystolic expanders have the topological overlapping property. No construction (either random or explicit) of bounded degree combinational expanders (according to either definition) were known until a recent work of Kaufman, Kazhdan and Lubotzky, which provided the first bounded degree cosystolic expanders of dimension two. No bounded degree combinatorial expanders are known in higher dimensions. In this work we present explicit bounded degree cosystolic expanders of every dimension. This solves affirmatively an open question raised by Gromov, who asked whether there exist bounded degree complexes with the topological overlapping property in every dimension. Moreover, we provide a local to global criterion on a complex that implies cosystolic expansion: Namely, for a ddimensional complex, X, if its underlying graph is a good expander, and all its links are both coboundary expanders and good expander graphs, then the (d - 1)-dimensional skeleton of the complex is a cosystolic expander.

AB - In recent years a high dimensional theory of expanders has emerged. The notion of combinatorial expansion of graphs (i.e. the Cheeger constant of a graph) has seen two generalizations to high dimensional simplicial complexes. One generalization, known as coboundary expansion, is due to Linial and Meshulem; the other, which we term here cosystolic expansion, is due to Gromov, who showed that cosystolic expanders have the topological overlapping property. No construction (either random or explicit) of bounded degree combinational expanders (according to either definition) were known until a recent work of Kaufman, Kazhdan and Lubotzky, which provided the first bounded degree cosystolic expanders of dimension two. No bounded degree combinatorial expanders are known in higher dimensions. In this work we present explicit bounded degree cosystolic expanders of every dimension. This solves affirmatively an open question raised by Gromov, who asked whether there exist bounded degree complexes with the topological overlapping property in every dimension. Moreover, we provide a local to global criterion on a complex that implies cosystolic expansion: Namely, for a ddimensional complex, X, if its underlying graph is a good expander, and all its links are both coboundary expanders and good expander graphs, then the (d - 1)-dimensional skeleton of the complex is a cosystolic expander.

KW - Cosystolic expanders

KW - High dimensional expanders

KW - Ramanujan complexes

KW - Topological overlapping

UR - http://www.scopus.com/inward/record.url?scp=84979249526&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84979249526&partnerID=8YFLogxK

U2 - 10.1145/2897518.2897543

DO - 10.1145/2897518.2897543

M3 - Conference contribution

AN - SCOPUS:84979249526

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 36

EP - 48

BT - STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Mansour, Yishay

A2 - Wichs, Daniel

PB - Association for Computing Machinery

T2 - 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016

Y2 - 19 June 2016 through 21 June 2016

ER -