Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

By Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava. IEEE Annual Symposium on Foundations of Computer Science, 2013

459 citations recorded by the source corpus.

We prove that there exist infinite families of regular bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph. We also establish the existence of infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we prove the existence of infinite families of (c, d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by √c-1+√d-1, for all c, d ≥ q 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials".

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/ddab225c61734c8f620704e9be8915c93cb39fa1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Spectral graph theory (2019, background): “[18] Given a d-regular graph G, there exists a 2-lift of G, G2 such that λ2(G2) ≤ 2 √ d− 1 Note that this theorem gives no control over λn.”
Interlacing families II: Mixed characteristic polynomials and the Kadison{Singer problem (2013, methodology): “We now recall the deﬁnition of interlacing families of polynomials from [41] and its main consequence.”
Expander graph and communication-efficient decentralized optimization (2016, background): “On the other hand, we agree for consensus averaging, those matrices recommended serve as the best candidates.”
Random Projections, Graph Sparsification, and Differential Privacy (2013, background): “The utility guarantee follows by incorporating the approximation guarantee provided by Spielman and Teng [32] or Spielman and Srivastava [31] in the analysis of Theorem 3.”
Cutoff on all Ramanujan graphs (2015, background): “That Corollaries 2–3 also cover bipartite Ramanujan graphs (recently shown to exist for every degree d ≥ 3 in [27]) follows form an extension of the proof of Theorem 1 to the bipartite setting (see Corollary 3.”
Universal Matrix Completion (2014, background): “Moreover, (Marcus et al., 2013) showed that bipartite Ramanujan graphs exist for all n and d .”
A new proof of Friedman's second eigenvalue theorem and its extension to random lifts (2015, background): “Proving the existence of Ramanujan graphs with a large number of vertices is a difficult task which has been solved for arbitrary d ≥ 3 only recently [21].”
Polynomial convolutions and (nite) free probability (2021, methodology): “The remainder of the proof then lies in building an “interlacing family” as developed in [19] that allows one to translate bounds on the roots of this Laguerre polynomial to bounds on the roots of individual polynomial.”