Explicit Two-Sided Vertex Expanders beyond the Spectral Barrier

We construct the first explicit two-sided vertex expanders that bypass the spectral barrier. Previously, the strongest known explicit vertex expanders were given by d-regular Ramanujan graphs, whose spectral properties imply that every small subset of vertices S has at least 0.5d|S| distinct neighbors. However, it is possible to construct Ramanujan graphs containing a small set S with no more than 0.5d|S| neighbors. In fact, no explicit construction was known to break the 0.5d-barrier. In this work, we give an explicit construction of an infinite family of d-regular graphs (for large enough d) where every small set expands by a factor of ≈ 0.6d. More generally, for large enough d 1 , d 2 , we give an infinite family of (d 1 , d 2 )-biregular graphs where small sets on the left expand by a factor of ≈ 0.6d 1 , and small sets on the right expand by a factor of ≈ 0.6d 2 . In fact, our construction satisfies an even stronger property: small sets on the left and right have unique-neighbor expansion 0.6d 1 and 0.6d 2 respectively. Our construction follows the tripartite line product framework of [HMMP24], and instantiates it using the face-vertex incidence of the 4-dimensional Ramanujan clique complex as its base component. As a key part of our analysis, we derive new bounds on the triangle density of small sets in the Ramanujan clique complex.