High-girth near-Ramanujan graphs with lossy vertex expansion

Theo McKenzie, Sidhanth Mohanty

Kahale proved that linear sized sets in $d$-regular Ramanujan graphs have vertex expansion $\sim \frac{d}{2}$ and complemented this with construction of near-Ramanujan graphs with v…