Interlacing families I: Bipartite Ramanujan graphs of all degrees

Adam Marcus, Daniel A. Spielman, Nikhil Srivastava

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 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 b√ipartite graphs with all non-trivial eigenvalues bounded by c - 1 + √ d - 1, for all c, d ≥ 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials".

Original languageEnglish (US)
Title of host publicationProceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Pages529-537
Number of pages9
DOIs
StatePublished - Dec 1 2013
Externally publishedYes
Event2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States
Duration: Oct 27 2013Oct 29 2013

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
CountryUnited States
CityBerkeley, CA
Period10/27/1310/29/13

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Lifts of graphs
  • Matching polynomial
  • Ramanujan graph

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

  • Cite this

    Marcus, A., Spielman, D. A., & Srivastava, N. (2013). Interlacing families I: Bipartite Ramanujan graphs of all degrees. In Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 (pp. 529-537). [6686189] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2013.63