### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Yishay Mansour, Daniel Wichs |

Publisher | Association for Computing Machinery |

Pages | 36-48 |

Number of pages | 13 |

ISBN (Electronic) | 9781450341325 |

DOIs | |

State | Published - Jun 19 2016 |

Externally published | Yes |

Event | 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States Duration: Jun 19 2016 → Jun 21 2016 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 19-21-June-2016 |

ISSN (Print) | 0737-8017 |

### Other

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

Country | United States |

City | Cambridge |

Period | 6/19/16 → 6/21/16 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Cosystolic expanders
- High dimensional expanders
- Ramanujan complexes
- Topological overlapping

## Cite this

*STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing*(pp. 36-48). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 19-21-June-2016). Association for Computing Machinery. https://doi.org/10.1145/2897518.2897543