EXPLICIT EXPANDERS OF EVERY DEGREE AND SIZE

An (n, d, lambda)-graph is a d regular graph on n vertices in which the absolute value of any nontrivial eigenvalue is at most lambda. For any constant d >= 3, epsilon > 0 and all sufficiently large n we show that there is a deterministic poly(n) time algorithm that outputs an (n, d, lambda)-graph (on exactly n vertices) with lambda <= 2d-1+epsilon. For any d=p+2 with p equivalent to 1 mod 4 prime and all sufficiently large n, we describe a strongly explicit construction of an (n; d;lambda)-graph (on exactly n vertices) with lambda <= root 2(d-1) + root d - 2) +o(1) (< 1 + root 2) root d - 1 + p (1)), with the o(1) term tending to 0 as n tends to infinity. For every epsilon > 0, d > d(0)(epsilon) and n>n(0)(d; epsilon) we present a strongly explicit construction of an (m;d;lambda)-graph with lambda<(2+epsilon)root d and m=n+o(n). All constructions are obtained by starting with known Ramanujan or nearly Ramanujan graphs and modifying or packing them in an appropriate way. The spectral analysis relies on the delocalization of eigenvectors of regular graphs in cycle-free neighborhoods.