## 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 - 2018 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics

## Keywords

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