Explicit Lossless Vertex Expanders

We give the first construction of explicit constantdegree lossless vertex expanders. Specifically, for any $\varepsilon\gt 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-2 \varepsilon) 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 [1] 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.