Explicit Lossless Vertex Expanders

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-2varepsilon)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.