2013

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

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

Understand

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.

Built on

Theory of monomer-dimer systems
O. J. Heilmann and E. H. Lieb · 1972
Earlier work this paper cites.
Zeros of convex combinations of polynomials
H. J. Fell · 1980
Earlier work this paper cites.
Functional Analysis
M. Reed and B. Simon · 1980
Earlier work this paper cites.
Matchings and walks in graphs
C. D. Godsil · 1981
Earlier work this paper cites.
On the matching polynomial of a graph
C. D. Godsil and I. Gutman · 1981
Earlier work this paper cites.
Walk generating functions and spectral measures of infinite graphs
C. D. Godsil and B. Mohar · 1988
Earlier work this paper cites.
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.
Ramanujan graphs and Hecke operators
A. K. Pizer · 1990
Earlier work this paper cites.
On the second eigenvalue of a graph
A. Nilli · 1991
Earlier work this paper cites.
Cubic Ramanujan graphs
P. Chiu · 1992
Earlier work this paper cites.
Obreschkoff’s theorem revisited: what convex sets are contained in the set of hyperbolic polynomials?
J. P. Dedieu · 1992
Earlier work this paper cites.
Algebraic combinatorics
C. Godsil · 1993
Earlier work this paper cites.
Discrete Groups, Expanding Graphs and Invariant Measures
A. Lubotzky · 1994
Earlier work this paper cites.
Existance and explicit constructions of q + 1 q+1 regular Ramanujan graphs for every prime power q q
M. Morgenstern · 1994
Earlier work this paper cites.

Similar

On the spectrum of graphs and their universal covering
Y. Greenberg · 1995
Cited alongside, same era.
Spectra of hypergraphs and applications
K. Feng and W.-C. W. Li · 1996
Cited alongside, same era.
Spectra of regular graphs and hypergraphs and orthogonal polynomials
W.-C. W. Li and P. Solé · 1996
Cited alongside, same era.
Expander codes
M. Sipser and D. Spielman · 1996
Cited alongside, same era.
Ramanujan local systems on graphs
B. W. Jordan and R. Livné · 1997
Cited alongside, same era.
Not every uniform tree covers Ramanujan graphs
A. Lubotzky and T. Nagnibeda · 1998
Cited alongside, same era.
On expander codes
G. Zémor · 2001
Cited alongside, same era.
Random lifts of graphs: independence and chromatic number
A. Amit, N. Linial, and J. Matoušek · 2002
Cited alongside, same era.
Relative expanders or weakly relatively Ramanujan graphs
J. Friedman · 2003
Cited alongside, same era.
Random lifts of graphs: perfect matchings
N. Linial and E. Rozenman · 2005
Cited alongside, same era.
Random lifts of graphs: edge expansion
A. Amit and N. Linial · 2006
Cited alongside, same era.
Decoding of expander codes at rates close to capacity
A. Ashikhmin and V. Skachek · 2006
Cited alongside, same era.

Then

Expander graphs and their applications
S. Hoory, N. Linial, and A. Wigderson · 2006
Later among the works it cites.
Improved nearly-mds expander codes
R. M. Roth and V. Skachek · 2006
Later among the works it cites.
The roots of the independence polynomial of a clawfree graph
M. Chudnovsky and P. Seymour · 2007
Later among the works it cites.
Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products
J. Borcea and P. Brändén · 2008
Later among the works it cites.
A proof of Alon’s second eigenvalue conjecture and related problems
J. Friedman · 2008
Later among the works it cites.
Matrix algebra from a statistician’s perspective
D. A. Harville · 2008
Later among the works it cites.
The spectrum of random lifts
Original
L. Addario-Berry and S. Griffiths · 2010
Later among the works it cites.
Multivariate Polya-Schur classification problems in the Weyl algebra
P. Brändén and J. Borcea · 2010
Later among the works it cites.
Word maps and spectra of random graph lifts
N. Linial and D. Puder · 2010
Later among the works it cites.
Spectra of lifted Ramanujan graphs
E. Lubetzky, B. Sudakov, and V. Vu · 2011
Later among the works it cites.
Multivariate stable polynomials: theory and applications
D. G. Wagner · 2011
Later among the works it cites.
Hyperbolicity and stable polynomials in combinatorics and probability
Original
R. Pemantle · 2012
Later among the works it cites.
Expansion of random graphs: New proofs, new results
Original
D. Puder · 2012
Later among the works it cites.
Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem
Original
A. Marcus, D. A. Spielman, and N. Srivastava · 2013
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…

Reading the bibliography…