Explicit Two-Sided Unique-Neighbor Expanders
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-ne...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155660 |
| _version_ | 1826209474146205696 |
|---|---|
| author | Hsieh, Jun-Ting McKenzie, Theo Mohanty, Sidhanth Paredes, Pedro |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Hsieh, Jun-Ting McKenzie, Theo Mohanty, Sidhanth Paredes, Pedro |
| author_sort | Hsieh, Jun-Ting |
| collection | MIT |
| description | 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 and the routed product of previous well-known works. 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 previously known results, 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 (d1,d2)-biregular graphs (Gn)n≥ 1 (for large enough d1 and d2) where all sets S with fewer than a small constant fraction of vertices have Ω(d1· |S|) unique-neighbors (assuming d1 ≤ d2). Additionally, we can also guarantee that subsets of vertices of size up to exp(Ω(√log|V(Gn)|)) expand losslessly. |
| first_indexed | 2024-09-23T14:23:06Z |
| format | Article |
| id | mit-1721.1/155660 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:23:46Z |
| publishDate | 2024 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1556602025-01-08T04:32:58Z Explicit Two-Sided Unique-Neighbor Expanders Hsieh, Jun-Ting McKenzie, Theo Mohanty, Sidhanth Paredes, Pedro Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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 and the routed product of previous well-known works. 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 previously known results, 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 (d1,d2)-biregular graphs (Gn)n≥ 1 (for large enough d1 and d2) where all sets S with fewer than a small constant fraction of vertices have Ω(d1· |S|) unique-neighbors (assuming d1 ≤ d2). Additionally, we can also guarantee that subsets of vertices of size up to exp(Ω(√log|V(Gn)|)) expand losslessly. 2024-07-11T20:40:51Z 2024-07-11T20:40:51Z 2024-06-10 2024-07-01T07:50:14Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155660 STOC ’24, June 24–28, 2024, Vancouver, BC, Canada PUBLISHER_CC en 10.1145/3618260.3649705 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The author(s) application/pdf ACM Association for Computing Machinery |
| spellingShingle | Hsieh, Jun-Ting McKenzie, Theo Mohanty, Sidhanth Paredes, Pedro Explicit Two-Sided Unique-Neighbor Expanders |
| title | Explicit Two-Sided Unique-Neighbor Expanders |
| title_full | Explicit Two-Sided Unique-Neighbor Expanders |
| title_fullStr | Explicit Two-Sided Unique-Neighbor Expanders |
| title_full_unstemmed | Explicit Two-Sided Unique-Neighbor Expanders |
| title_short | Explicit Two-Sided Unique-Neighbor Expanders |
| title_sort | explicit two sided unique neighbor expanders |
| url | https://hdl.handle.net/1721.1/155660 |
| work_keys_str_mv | AT hsiehjunting explicittwosideduniqueneighborexpanders AT mckenzietheo explicittwosideduniqueneighborexpanders AT mohantysidhanth explicittwosideduniqueneighborexpanders AT paredespedro explicittwosideduniqueneighborexpanders |