TY - JOUR

T1 - Interlacing families I

T2 - Bipartite Ramanujan graphs of all degrees

AU - Marcus, Adam W.

AU - Spielman, Daniel A.

AU - Srivastava, Nikhil

N1 - Publisher Copyright:
© 2015 Department of Mathematics, Princeton University.

PY - 2015

Y1 - 2015

N2 - We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of "irregular Ramanujan" graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c, d)-biregular bipartite graphs with all nontrivial eigenvalues bounded by √c-1+ √d-1 for all c, d ≥ 3. Our proof exploits a new technique for controlling the eigenvalues of certain random matrices, which we call the "method of interlacing polynomials."

AB - We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of "irregular Ramanujan" graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c, d)-biregular bipartite graphs with all nontrivial eigenvalues bounded by √c-1+ √d-1 for all c, d ≥ 3. Our proof exploits a new technique for controlling the eigenvalues of certain random matrices, which we call the "method of interlacing polynomials."

UR - http://www.scopus.com/inward/record.url?scp=84929084008&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84929084008&partnerID=8YFLogxK

U2 - 10.4007/annals.2015.182.1.7

DO - 10.4007/annals.2015.182.1.7

M3 - Article

AN - SCOPUS:84929084008

VL - 182

SP - 307

EP - 325

JO - Annals of Mathematics

JF - Annals of Mathematics

SN - 0003-486X

IS - 1

ER -