TY - JOUR
T1 - Explicit Expanders of Every Degree and Size
AU - Alon, Noga
N1 - Funding Information:
Research supported in part by NSF grant DMS-1855464, ISF grant 281/17, BSF grant 2018267 and the Simons Foundation. Acknowledgment
Publisher Copyright:
© 2021, János Bolyai Mathematical Society and Springer-Verlag.
PY - 2021/8
Y1 - 2021/8
N2 - An (n, d, λ)-graph is a d regular graph on n vertices in which the absolute value of any nontrivial eigenvalue is at most λ. For any constant d ≥ 3, ϵ > 0 and all sufficiently large n we show that there is a deterministic poly(n) time algorithm that outputs an (n, d, λ)-graph (on exactly n vertices) with λ≤2d−1+ϵ. For any d=p + 2 with p ≡ 1 mod 4 prime and all sufficiently large n, we describe a strongly explicit construction of an (n, d, λ)-graph (on exactly n vertices) with λ≤2(d−1)+d−2+o(1)(<(1+2)d−1+o(1)), with the o(1) term tending to 0 as n tends to infinity. For every ϵ> 0, d> d0(ϵ) and n>n0(d, ϵ) we present a strongly explicit construction of an (m, d, λ)-graph with λ<(2+ϵ)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.
AB - An (n, d, λ)-graph is a d regular graph on n vertices in which the absolute value of any nontrivial eigenvalue is at most λ. For any constant d ≥ 3, ϵ > 0 and all sufficiently large n we show that there is a deterministic poly(n) time algorithm that outputs an (n, d, λ)-graph (on exactly n vertices) with λ≤2d−1+ϵ. For any d=p + 2 with p ≡ 1 mod 4 prime and all sufficiently large n, we describe a strongly explicit construction of an (n, d, λ)-graph (on exactly n vertices) with λ≤2(d−1)+d−2+o(1)(<(1+2)d−1+o(1)), with the o(1) term tending to 0 as n tends to infinity. For every ϵ> 0, d> d0(ϵ) and n>n0(d, ϵ) we present a strongly explicit construction of an (m, d, λ)-graph with λ<(2+ϵ)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.
UR - http://www.scopus.com/inward/record.url?scp=85100277678&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85100277678&partnerID=8YFLogxK
U2 - 10.1007/s00493-020-4429-x
DO - 10.1007/s00493-020-4429-x
M3 - Article
AN - SCOPUS:85100277678
SN - 0209-9683
VL - 41
SP - 447
EP - 463
JO - Combinatorica
JF - Combinatorica
IS - 4
ER -