Fetching the paper…

Reading the bibliography…

2015

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

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

Original
PDF
Post on X

Understand

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 we recently introduced.

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes · Around

Built on

Ramanujan graphs
A. Lubotzky, R. Phillips, and P. Sarnak · 1988
Earlier work this paper cites.
Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
G. A. Margulis · 1988
Earlier work this paper cites.
On the second eigenvalue of a graph
A. Nilli · 1991
Earlier work this paper cites.
Lifts, discrepancy and nearly optimal spectral gap*
Yonatan Bilu and Nathan Linial · 2006
Earlier work this paper cites.

Similar

Expander graphs and their applications
Shlomo Hoory, Nathan Linial, and Avi Wigderson · 2006
Cited alongside, same era.
Polynomials, roots, and interlacing
Steve Fisk · 2008
Cited alongside, same era.
A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems
Joel Friedman · 2008
Cited alongside, same era.
Twice-Ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Cited alongside, same era.

Then

Hyperbolicity and stable polynomials in combinatorics and probability
Original
Robin Pemantle · 2012
Later among the works it cites.
Finite free convolutions of polynomials
Original
A. Marcus, D. A. Spielman, and N. Srivastava · 2015
Closest in time.
Interlacing families I: Bipartite Ramanujan graphs of all degrees
Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava · 2015
Closest in time.
Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem
Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava · 2015
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…