Explicit near-Ramanujan graphs of every degree
For every constant d ≥ 3 and ϵ > 0, we give a deterministic poly(n)-time algorithm that outputs a d-regular graph on Θ(n) vertices that is ϵ-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by 2√(d-1) + ϵ (excluding the single trivial eigenvalue of d).
READ FULL TEXT