Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

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

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

33 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
Country/TerritoryUnited States
CityBerkeley
Period10/17/1510/20/15

All Science Journal Classification (ASJC) codes

  • General Computer Science

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