Explicit near-Ramanujan graphs of every degree

Abstract

For every constant $d\ge 3$ and $\epsilon >0$, we give a deterministic $\mathrm{poly}(n)$-time algorithm that outputs a $d$-regular graph on $\Theta (n)$ vertices that is $\epsilon$-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by $2\sqrt{d-1}+\epsilon$ (excluding the single trivial eigenvalue of~$d$).

26 pages