Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

Abstract

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 sqrt{c-1}+sqrt{d-1}, for all c, d \geq 3. Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "method of interlacing polynomials'".

References in corpus (4)

• Expansion of Random Graphs: New Proofs, New Results
• Polynomials, roots, and interlacing
• Hyperbolicity and stable polynomials in combinatorics and probability
• The Lee-Yang and Pólya-Schur programs. III. Zero-preservers on Bargmann-Fock spaces

Cited by in corpus (25)

• Expansion of Random Graphs: New Proofs, New Results
• Quantum ergodicity on large regular graphs
• Universal Matrix Completion
• Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem
• Ramanujan Graphs and the Solution of the Kadison-Singer Problem
• Sparsified Cholesky Solvers for SDD linear systems
• The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP
• On the signed graphs with two distinct eigenvalues
• The Sketching Complexity of Graph Cuts
• Signatures, lifts, and eigenvalues of graphs
• Cutoff on Graphs and the Sarnak-Xue Density of Eigenvalues
• $L^p$ Expander Graphs
• An isoperimetric constant for signed graphs
• Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
• Real Stable Polynomials and Matroids: Optimization and Counting
• Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
• Towards Constructing Ramanujan Graphs Using Shift Lifts
• Real Stability Testing
• Atoms of the matching measure
• Cylindrical Graph Construction (definition and basic properties)
• A New [Combinatorial] Proof of the Commutativity of Matching Polynomials for Cycles
• Equitable partitions for Ramanajun graphs
• A Berry-Essen Type Theorem for Finite Free Convolution
• Median eigenvalues of bipartite graphs
• The Metric Relaxation for $0$-Extension Admits an $\Omega ({\log }^{2/3}k)$ Gap