Explicit two-sided unique-neighbor expanders
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916090516340736 |
|---|---|
| author | Hsieh, Jun-Ting McKenzie, Theo Mohanty, Sidhanth Paredes, Pedro |
| author_facet | Hsieh, Jun-Ting McKenzie, Theo Mohanty, Sidhanth Paredes, Pedro |
| contents | We study the problem of constructing explicit sparse graphs that exhibit strong vertex expansion. Our main result is the first two-sided construction of imbalanced unique-neighbor expanders, meaning bipartite graphs where small sets contained in both the left and right bipartitions exhibit unique-neighbor expansion, along with algebraic properties relevant to constructing quantum codes.
Our constructions are obtained from instantiations of the tripartite line product of a large tripartite spectral expander and a sufficiently good constant-sized unique-neighbor expander, a new graph product we defined that generalizes the line product in the work of Alon and Capalbo and the routed product in the work of Asherov and Dinur.
To analyze the vertex expansion of graphs arising from the tripartite line product, we develop a sharp characterization of subgraphs that can arise in bipartite spectral expanders, generalizing results of Kahale, which may be of independent interest.
By picking appropriate graphs to apply our product to, we give a strongly explicit construction of an infinite family of $(d_1,d_2)$-biregular graphs $(G_n)_{n\ge 1}$ (for large enough $d_1$ and $d_2$) where all sets $S$ with fewer than a small constant fraction of vertices have $Ω(d_1\cdot |S|)$ unique-neighbors (assuming $d_1 \leq d_2$).
Additionally, we can also guarantee that subsets of vertices of size up to $\exp(Ω(\sqrt{\log |V(G_n)|}))$ expand losslessly. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_01212 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Explicit two-sided unique-neighbor expanders Hsieh, Jun-Ting McKenzie, Theo Mohanty, Sidhanth Paredes, Pedro Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms 05C48 G.2.1; G.2.2 We study the problem of constructing explicit sparse graphs that exhibit strong vertex expansion. Our main result is the first two-sided construction of imbalanced unique-neighbor expanders, meaning bipartite graphs where small sets contained in both the left and right bipartitions exhibit unique-neighbor expansion, along with algebraic properties relevant to constructing quantum codes. Our constructions are obtained from instantiations of the tripartite line product of a large tripartite spectral expander and a sufficiently good constant-sized unique-neighbor expander, a new graph product we defined that generalizes the line product in the work of Alon and Capalbo and the routed product in the work of Asherov and Dinur. To analyze the vertex expansion of graphs arising from the tripartite line product, we develop a sharp characterization of subgraphs that can arise in bipartite spectral expanders, generalizing results of Kahale, which may be of independent interest. By picking appropriate graphs to apply our product to, we give a strongly explicit construction of an infinite family of $(d_1,d_2)$-biregular graphs $(G_n)_{n\ge 1}$ (for large enough $d_1$ and $d_2$) where all sets $S$ with fewer than a small constant fraction of vertices have $Ω(d_1\cdot |S|)$ unique-neighbors (assuming $d_1 \leq d_2$). Additionally, we can also guarantee that subsets of vertices of size up to $\exp(Ω(\sqrt{\log |V(G_n)|}))$ expand losslessly. |
| title | Explicit two-sided unique-neighbor expanders |
| topic | Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms 05C48 G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2302.01212 |