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-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 [AC02] and the routed product in the work of Asherov and Dinur [AD23]. 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 [Kah95], 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⩾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 • |S|) unique-neighbors (assuming d 1 ⩽ d 2 ). Additionally, we can also guarantee that subsets of vertices of size up to exp(Ω( log |V(G n )|)) expand losslessly.