Explicit near-Ramanujan graphs of every degree

09/16/2019
by   Sidhanth Mohanty, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset