Geodesic
Interlacing families I: Bipartite Ramanujan graphs of all degrees
Adam W. Marcus1 ; Daniel A. Spielman2 ; Nikhil Srivastava3
1 Department of Mathematics, Yale University, PO Box 208283, New Haven, CT 06520-8283
2 Yale Institute for Network Science, PO Box 208263, 17 Hillhouse Ave., New Haven, CT 06520-8263
3 Microsoft Research, "Vigyan", #9, Lavelle Road, Bangalore 560 001, India
Annals of mathematics, Tome 182 (2015) no. 1, pp. 307-325.

Voir la notice de l'article provenant de la source Annals of Mathematics website

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 nontrivial eigenvalues bounded by $\sqrt{c-1}+\sqrt{d-1}$ for all $c, d \geq 3$. Our proof exploits a new technique for controlling the eigenvalues of certain random matrices, which we call the “method of interlacing polynomials.”
DOI : 10.4007/annals.2015.182.1.7

Adam W. Marcus 1 ; Daniel A. Spielman 2 ; Nikhil Srivastava 3

1 Department of Mathematics, Yale University, PO Box 208283, New Haven, CT 06520-8283
2 Yale Institute for Network Science, PO Box 208263, 17 Hillhouse Ave., New Haven, CT 06520-8263
3 Microsoft Research, "Vigyan", #9, Lavelle Road, Bangalore 560 001, India 
@article{10_4007_annals_2015_182_1_7,
     author = {Adam W. Marcus and Daniel A. Spielman and Nikhil Srivastava},
     title = {Interlacing families {I:} {Bipartite} {Ramanujan} graphs of all degrees},
     journal = {Annals of mathematics},
     pages = {307--325},
     publisher = {mathdoc},
     volume = {182},
     number = {1},
     year = {2015},
     doi = {10.4007/annals.2015.182.1.7},
     mrnumber = {3374962},
     zbl = {06456011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2015.182.1.7/}
}
TY  - JOUR
AU  - Adam W. Marcus
AU  - Daniel A. Spielman
AU  - Nikhil Srivastava
TI  - Interlacing families I: Bipartite Ramanujan graphs of all degrees
JO  - Annals of mathematics
PY  - 2015
SP  - 307
EP  - 325
VL  - 182
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2015.182.1.7/
DO  - 10.4007/annals.2015.182.1.7
LA  - en
ID  - 10_4007_annals_2015_182_1_7
ER  - 
%0 Journal Article
%A Adam W. Marcus
%A Daniel A. Spielman
%A Nikhil Srivastava
%T Interlacing families I: Bipartite Ramanujan graphs of all degrees
%J Annals of mathematics
%D 2015
%P 307-325
%V 182
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2015.182.1.7/
%R 10.4007/annals.2015.182.1.7
%G en
%F 10_4007_annals_2015_182_1_7
Adam W. Marcus; Daniel A. Spielman; Nikhil Srivastava. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Annals of mathematics, Tome 182 (2015) no. 1, pp. 307-325. doi : 10.4007/annals.2015.182.1.7. http://geodesic.mathdoc.fr/articles/10.4007/annals.2015.182.1.7/

Cité par Sources :