Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

Adam Wade Marcus, Daniel A. Spielman, Nikhil Srivastava

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

21 Scopus citations

Abstract

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on analyzing the expected characteristic polynomial of a union of random perfect matchings, and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real rooted and that the family of polynomials considered in this sum is an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions introduced recently by the authors.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PublisherIEEE Computer Society
Pages1358-1377
Number of pages20
ISBN (Electronic)9781467381918
DOIs
StatePublished - Dec 11 2015
Event56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States
Duration: Oct 17 2015Oct 20 2015

Publication series

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

Other

Other56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
CountryUnited States
CityBerkeley
Period10/17/1510/20/15

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Ramanujan graphs
  • expected characteristic polynomials
  • finite free probability

Fingerprint Dive into the research topics of 'Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes'. Together they form a unique fingerprint.

  • Cite this

    Marcus, A. W., Spielman, D. A., & Srivastava, N. (2015). Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. In Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 (pp. 1358-1377). [7354461] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2015-December). IEEE Computer Society. https://doi.org/10.1109/FOCS.2015.87