TY - GEN

T1 - Explicit Two-Sided Unique-Neighbor Expanders

AU - Hsieh, Jun Ting

AU - McKenzie, Theo

AU - Mohanty, Sidhanth

AU - Paredes, Pedro

N1 - Publisher Copyright:
© 2024 Owner/Author.

PY - 2024/6/10

Y1 - 2024/6/10

N2 - 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.

AB - 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.

KW - Algebraic expanders

KW - Lossless expanders

KW - Unique-neighbor expanders

UR - http://www.scopus.com/inward/record.url?scp=85196658653&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85196658653&partnerID=8YFLogxK

U2 - 10.1145/3618260.3649705

DO - 10.1145/3618260.3649705

M3 - Conference contribution

AN - SCOPUS:85196658653

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 788

EP - 799

BT - STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing

A2 - Mohar, Bojan

A2 - Shinkar, Igor

A2 - O�Donnell, Ryan

PB - Association for Computing Machinery

T2 - 56th Annual ACM Symposium on Theory of Computing, STOC 2024

Y2 - 24 June 2024 through 28 June 2024

ER -