Interlacing families I: Bipartite Ramanujan graphs of all degrees

Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava

Research output: Contribution to journalArticle

66 Scopus citations

Abstract

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."

Original languageEnglish (US)
Pages (from-to)307-325
Number of pages19
JournalAnnals of Mathematics
Volume182
Issue number1
DOIs
StatePublished - Jan 1 2015

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Interlacing families I: Bipartite Ramanujan graphs of all degrees'. Together they form a unique fingerprint.

  • Cite this