Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-196 | 27th November 2025 11:14

Ultra-Sparse Expanders and the Free Method

RSS-Feed




TR25-196
Authors: Gil Cohen, Gal Maor
Publication: 30th November 2025 08:39
Downloads: 41
Keywords: 


Abstract:

In this paper we ask how much expansion one can retain with almost no edges beyond connectivity. Concretely, for graphs of average degree $2+\varepsilon$, what is the “Ramanujan bound’’—how does spectral expansion scale with $\varepsilon$? We compare five ultra–sparse graph models—including the configuration model, subdivision of regular expanders, and the union of a cycle with a partial matching—and analyze each under the normalized or unnormalized notions of expansion.

For some models we prove rigorous bounds—primarily via finite free probability—while others remain beyond our current techniques. To bridge this gap, we introduce the Free Method, which produces quantitative predictions without proving existence—analogous to the probabilistic method, which certifies existence without providing an explicit construction. These predictions align with experiments. We expect the free method to be useful more broadly in graph-theoretic settings.

Our results also extend to expansion in general irregular graphs. Moreover, as a byproduct, we give two alternative proofs of the Marcus–Spielman–Srivastava existence theorem for one-sided Ramanujan graphs.



ISSN 1433-8092 | Imprint