ECCC-Report TR24-102https://eccc.weizmann.ac.il/report/2024/102Comments and Revisions published for TR24-102en-usSun, 09 Jun 2024 13:18:51 +0300
Paper TR24-102
| Sparse High Dimensional Expanders via Local Lifts |
Inbar Ben Yaacov,
Yotam Dikstein,
Gal Maor
https://eccc.weizmann.ac.il/report/2024/102High dimensional expanders (HDXs) are a hypergraph generalization of expander graphs. They are extensively studied in the math and TCS communities due to their many applications. Like expander graphs, HDXs are especially interesting for applications when they are bounded degree, namely, if the number of edges adjacent to every vertex is bounded. However, only a handful of constructions are known to have this property, all of which rely on non-trivial algebraic techniques. In particular, no random or combinatorial construction of bounded degree high dimensional expanders is known. As a result, our understanding of these objects is limited.
The degree of an $i$-face in an HDX is the number of $(i+1)$-faces that contain it. In this work we construct complexes whose higher dimensional faces have bounded degree. This is done by giving an elementary and deterministic algorithm that takes as input a regular $k$-dimensional HDX $X$ and outputs another regular $k$-dimensional HDX $\widehat{X}$ with twice as many vertices. While the degree of vertices in $\widehat{X}$ grows, the degree of the $(k-1)$-faces in $\widehat{X}$ stays the same. As a result, we obtain a new `algebra-free' construction of HDXs whose $(k-1)$-face degree is bounded.
Our construction algorithm is based on a simple and natural generalization of the expander graph construction by Bilu and Linial (Combinatorica, 2006), which build expander graphs using lifts coming from edge signings. Our construction is based on local lifts of high dimensional expanders, where a local lift is a new complex whose top-level links are lifts of the links of the original complex. We demonstrate that a local lift of an HDX is also an HDX in many cases.
In addition, combining local lifts with existing bounded degree constructions creates new families of bounded degree HDXs with significantly different links than before. We use this technique to construct bounded degree high dimensional expanders with links that have arbitrarily large diameters.Sun, 09 Jun 2024 13:18:51 +0300https://eccc.weizmann.ac.il/report/2024/102