2025/04/21 by Hsieh, Jun-Ting, Lubotzky, Alexander, Mohanty, Sidhanth +2 · 8 citations
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR)
paper · doi:10.48550/arxiv.2504.15087
We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any ε > 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-ε)d|S| neighbors (which implies (1-2ε)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.