Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
Authors:
- Adam MarcusAMAdam Marcus
- Daniel A. SpielmanDSDaniel A. Spielman
- Nikhil SrivastavaNSNikhil Srivastava
- 1 October 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 529-537
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 √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".Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Expander graphs and their applicationsBulletin of the American Mathematical Society, 2006
- Eigenvalues of graphs and a simple proof of a theorem of GreenbergLinear Algebra and its Applications, 2006
- Relative expanders or weakly relatively Ramanujan graphsDuke Mathematical Journal, 2003
- Not Every Uniform Tree Covers Ramanujan GraphsJournal of Combinatorial Theory, Series B, 1998
- Spectra of Hypergraphs and ApplicationsJournal of Number Theory, 1996
- Spectra of Regular Graphs and Hypergraphs and Orthogonal PolynomialsEuropean Journal of Combinatorics, 1996
- Obreschkoff's theorem revisited: what convex sets are contained in the set of hyperbolic polynomials?Journal of Pure and Applied Algebra, 1992
- Walk generating functions and spectral measures of infinite graphsLinear Algebra and its Applications, 1988
- Matchings and walks in graphsJournal of Graph Theory, 1981
- On the zeros of convex combinations of polynomialsPacific Journal of Mathematics, 1980