Explicit Lossless Vertex Expanders!
Combinatorics and more 2025-10-10
(from left to right): Beth Samuels, Uzi Vishne, Alex Lubotzky, and Winnie Li
Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, and Rachel Yun Zhang, Explicit Lossless Vertex Expanders
Abstract: We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any 
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.
Additional commentary. Expander graphs play a central role in mathematics and computer science. While random graphs typically have excellent expansion, constructing explicit families with comparable guarantees has been a central challenge for the past fifty years. For large vertex sets, expansion can be derived from certain spectral properties of the graph; for small sets, however, explicitly matching random-like behavior is far harder. The remarkable new paper meets this challenge by using high-dimensional Ramanujan cubical complexes. In earlier work [1], the 1/2 barrier for spectral methods was surpassed via certain five-dimensional Ramanujan simplicial complexes. Extending to higher dimensions had been hindered by irregular link structures in those complexes, but it turns out that specific cubical Ramanujan complexes—tracing back to Jordan and Livné [5]—circumvent this obstacle.
Alex jokingly credits the breakthrough to Donald Trump: a planned MIT event was canceled for an urgent meeting on the impact of Trump-era measures on MIT mathematics. Instead, Alex joined a lunch with graduate students; that conversation led to an impromptu seminar and, ultimately, to the new collaboration.
[1] Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty, Ryan O’Donnell, and Rachel Yun Zhang. Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025.
Ramanujan complexes
Ramanujan complexes are high-dimensional extensions of Ramanujan graphs: finite, bounded-degree complexes whose set of eigenvalues are “as small as they can be”—namely, contained in the spectrum of their infinite universal cover. This optimal spectral control drives strong expansion—combinatorial, and topological.
Ramanujan complexes were constructed and studied in the early 2000s by Winnie Li and by Alex Lubotzky, Beth Samuels, and Uzi Vishne. (In the picture above, from left to right, Beth, Uzi, Alex and Winnie.)
[2] W.-C. W. Li, Ramanujan Hypergraphs, GAFA (2004)
[3] Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Explicit constructions of Ramanujan complexes of type 
[4] Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Ramanujan complexes of type
Some related early papers are:
[5] B.W. Jordan and R. Livné, The Ramanujan property for regular cubical complexes, Duke Mathematical Journal 105, 85–103, (2000)
[6] P. Sole, Ramanujan Hypergraphs and Ramanujan Geometries.
High dimensional expanders
Here is a brief introductury post for high dimensional expanders. Alex and I gave together several courses about this subject at HUJI and at Yale. Below is the ICM 2018 lecture in Rio by Alex on the topic.