How much expansion can one retain with almost no edges beyond connectivity? Concretely, for graphs of average degree 2 + ε, what is the right “Ramanujan bound” -- how should spectral expansion scale with ε? In this work we settle this question, showing that the optimal spectral gap is quadratic in ε. I will discuss natural constructions of such ultra-sparse graphs, focusing on random configuration graphs and subdivisions of regular expanders. The proofs are guided by free probability, which gives a way to reason about graph spectra through a noncommutative notion of independence.

---

Joint work with Gil Cohen