### Abstract

We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on an analysis of 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 language | English (US) |
---|---|

Pages (from-to) | 2488-2509 |

Number of pages | 22 |

Journal | SIAM Journal on Computing |

Volume | 47 |

Issue number | 6 |

DOIs | |

State | Published - Jan 1 2018 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)

### Keywords

- Expander graphs
- Free probability
- Interlacing
- Random graphs
- Random matrices

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

## Cite this

*SIAM Journal on Computing*,

*47*(6), 2488-2509. https://doi.org/10.1137/16M106176X