Explicit Lossless Vertex Expanders
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910915511713792 |
|---|---|
| author | Hsieh, Jun-Ting Lubotzky, Alexander Mohanty, Sidhanth Reiner, Assaf Zhang, Rachel Yun |
| author_facet | Hsieh, Jun-Ting Lubotzky, Alexander Mohanty, Sidhanth Reiner, Assaf Zhang, Rachel Yun |
| contents | We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any $\varepsilon > 0$ and sufficiently large $d$, we give an explicit construction of an infinite family of $d$-regular graphs where every small set $S$ of vertices has $(1-\varepsilon)d|S|$ neighbors (which implies $(1-2\varepsilon)d|S|$ unique-neighbors). Our results also extend naturally to construct biregular bipartite graphs of any constant imbalance, where small sets on each side have strong expansion guarantees. The graphs we construct admit a free group action, and hence realize new families of quantum LDPC codes of Lin and M. Hsieh with a linear time decoding algorithm.
Our construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from Ramanujan Cayley cubical complexes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15087 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Explicit Lossless Vertex Expanders Hsieh, Jun-Ting Lubotzky, Alexander Mohanty, Sidhanth Reiner, Assaf Zhang, Rachel Yun Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms Group Theory We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any $\varepsilon > 0$ and sufficiently large $d$, we give an explicit construction of an infinite family of $d$-regular graphs where every small set $S$ of vertices has $(1-\varepsilon)d|S|$ neighbors (which implies $(1-2\varepsilon)d|S|$ unique-neighbors). Our results also extend naturally to construct biregular bipartite graphs of any constant imbalance, where small sets on each side have strong expansion guarantees. The graphs we construct admit a free group action, and hence realize new families of quantum LDPC codes of Lin and M. Hsieh with a linear time decoding algorithm. Our construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from Ramanujan Cayley cubical complexes. |
| title | Explicit Lossless Vertex Expanders |
| topic | Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms Group Theory |
| url | https://arxiv.org/abs/2504.15087 |