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 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.”
-
[addario2010spectrum] L. Addario-Berry and S. Griffiths, The spectrum of random lifts, 2010.
@misc{addario2010spectrum,
author = {Addario-Berry, L. and Griffiths, S.},
title = {The spectrum of random lifts},
arxiv = {1012.4097},
year = {2010},
} -
[amit2006random]
A. Amit and N. Linial, "Random lifts of graphs: edge expansion," Combin. Probab. Comput., vol. 15, iss. 3, pp. 317-332, 2006.@article{amit2006random, mrkey = {2216470},
author = {Amit, Alon and Linial, Nathan},
title = {Random lifts of graphs: edge expansion},
journal = {Combin. Probab. Comput.},
fjournal = {Combinatorics, Probability and Computing},
volume = {15},
year = {2006},
number = {3},
pages = {317--332},
issn = {0963-5483},
mrclass = {05C80},
mrnumber = {2216470},
mrreviewer = {J{ó}zsef Balogh},
doi = {10.1017/S0963548305007273},
zblnumber = {1095.05034},
} -
[amit2002random] A. Amit, N. Linial, and J. Matouvsek, "Random lifts of graphs: independence and chromatic number," Random Structures Algorithms, vol. 20, iss. 1, pp. 1-22, 2002.
@article{amit2002random, mrkey = {1871947},
author = {Amit, Alon and Linial, Nathan and Matou{š}ek, Ji{\v{r}}{\'ı}},
title = {Random lifts of graphs: independence and chromatic number},
journal = {Random Structures Algorithms},
fjournal = {Random Structures \& Algorithms},
volume = {20},
year = {2002},
number = {1},
pages = {1--22},
issn = {1042-9832},
mrclass = {05C80 (05C15)},
mrnumber = {1871947},
mrreviewer = {Zbigniew Palka},
doi = {10.1002/rsa.10003},
zblnumber = {0993.05071},
} -
[BiluLinial] Y. Bilu and N. Linial, "Lifts, discrepancy and nearly optimal spectral gap," Combinatorica, vol. 26, iss. 5, pp. 495-519, 2006.
@article{BiluLinial, mrkey = {2279667},
author = {Bilu, Yonatan and Linial, Nathan},
title = {Lifts, discrepancy and nearly optimal spectral gap},
journal = {Combinatorica},
fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
volume = {26},
year = {2006},
number = {5},
pages = {495--519},
issn = {0209-9683},
mrclass = {05C50},
mrnumber = {2279667},
mrreviewer = {Sebastian M. Cioab{\u{a}}},
doi = {10.1007/s00493-006-0029-7},
zblnumber = {1121.05054},
} -
[borcea2008applications] J. Borcea and P. Brändén, "Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products," Duke Math. J., vol. 143, iss. 2, pp. 205-223, 2008.
@article{borcea2008applications, mrkey = {2420507},
author = {Borcea, Julius and Br{ä}nd{é}n, Petter},
title = {Applications of stable polynomials to mixed determinants: {J}ohnson's conjectures, unimodality, and symmetrized {F}ischer products},
journal = {Duke Math. J.},
fjournal = {Duke Mathematical Journal},
volume = {143},
year = {2008},
number = {2},
pages = {205--223},
issn = {0012-7094},
coden = {DUMJAO},
mrclass = {15A15 (30C15 32A60)},
mrnumber = {2420507},
mrreviewer = {Julio Ben{\'ı}tez},
doi = {10.1215/00127094-2008-018},
zblnumber = {1151.15013},
} -
[BBWeylAlgebra] J. Borcea and P. Brändén, "Multivariate Pólya-Schur classification problems in the Weyl algebra," Proc. Lond. Math. Soc., vol. 101, iss. 1, pp. 73-104, 2010.
@article{BBWeylAlgebra, mrkey = {2661242},
author = {Borcea, J. and Br{ä}nd{é}n, P.},
title = {Multivariate {P}ólya-{S}chur classification problems in the {W}eyl algebra},
journal = {Proc. Lond. Math. Soc.},
fjournal = {Proceedings of the London Mathematical Society. Third Series},
volume = {101},
year = {2010},
number = {1},
pages = {73--104},
issn = {0024-6115},
mrclass = {47B37 (15A15 16S32 32A17 32A60)},
mrnumber = {2661242},
mrreviewer = {Vania D. Mascioni},
doi = {10.1112/plms/pdp049},
zblnumber = {1196.47028},
} -
[chiu1992cubic] P. Chiu, "Cubic Ramanujan graphs," Combinatorica, vol. 12, iss. 3, pp. 275-285, 1992.
@article{chiu1992cubic, mrkey = {1195890},
author = {Chiu, Patrick},
title = {Cubic {R}amanujan graphs},
journal = {Combinatorica},
fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
volume = {12},
year = {1992},
number = {3},
pages = {275--285},
issn = {0209-9683},
coden = {COMBDI},
mrclass = {05C35 (05C75)},
mrnumber = {1195890},
mrreviewer = {Daniel Rockmore},
doi = {10.1007/BF01285816},
zblnumber = {0770.05062},
} -
[ChudnovskySeymour] M. Chudnovsky and P. Seymour, "The roots of the independence polynomial of a clawfree graph," J. Combin. Theory Ser. B, vol. 97, iss. 3, pp. 350-357, 2007.
@article{ChudnovskySeymour, mrkey = {2305888},
author = {Chudnovsky, Maria and Seymour, Paul},
title = {The roots of the independence polynomial of a clawfree graph},
journal = {J. Combin. Theory Ser. B},
fjournal = {Journal of Combinatorial Theory. Series B},
volume = {97},
year = {2007},
number = {3},
pages = {350--357},
issn = {0095-8956},
coden = {JCBTB8},
mrclass = {05C69},
mrnumber = {2305888},
mrreviewer = {Steven D. Noble},
doi = {10.1016/j.jctb.2006.06.001},
zblnumber = {1119.05075},
} -
[cioabua2006eigenvalues] S. M. Cioabua, "Eigenvalues of graphs and a simple proof of a theorem of Greenberg," Linear Algebra Appl., vol. 416, iss. 2-3, pp. 776-782, 2006.
@article{cioabua2006eigenvalues, mrkey = {2242462},
author = {Cioab{\u{a}},
Sebastian M.},
title = {Eigenvalues of graphs and a simple proof of a theorem of {G}reenberg},
journal = {Linear Algebra Appl.},
fjournal = {Linear Algebra and its Applications},
volume = {416},
year = {2006},
number = {2-3},
pages = {776--782},
issn = {0024-3795},
coden = {LAAPAW},
mrclass = {05C50},
mrnumber = {2242462},
doi = {10.1016/j.laa.2005.12.020},
zblnumber = {1109.05068},
} -
[Dedieu] J. Dedieu, "Obreschkoff’s theorem revisited: what convex sets are contained in the set of hyperbolic polynomials?," J. Pure Appl. Algebra, vol. 81, iss. 3, pp. 269-278, 1992.
@article{Dedieu, mrkey = {1179101},
author = {Dedieu, Jean-Pierre},
title = {Obreschkoff's theorem revisited: what convex sets are contained in the set of hyperbolic polynomials?},
journal = {J. Pure Appl. Algebra},
fjournal = {Journal of Pure and Applied Algebra},
volume = {81},
year = {1992},
number = {3},
pages = {269--278},
issn = {0022-4049},
coden = {JPAAA2},
mrclass = {12D10},
mrnumber = {1179101},
mrreviewer = {Thomas C. Craven},
doi = {10.1016/0022-4049(92)90060-S},
zblnumber = {0772.12002},
} -
[Fell] H. J. Fell, "On the zeros of convex combinations of polynomials," Pacific J. Math., vol. 89, iss. 1, pp. 43-50, 1980.
@article{Fell, mrkey = {0596914},
author = {Fell, H. J.},
title = {On the zeros of convex combinations of polynomials},
journal = {Pacific J. Math.},
fjournal = {Pacific Journal of Mathematics},
volume = {89},
year = {1980},
number = {1},
pages = {43--50},
issn = {0030-8730},
coden = {PJMAAI},
mrclass = {30C15},
mrnumber = {0596914},
mrreviewer = {M. Marden},
doi = {10.2140/pjm.1980.89.43},
zblnumber = {0416.30005},
} -
[FengLi] K. Feng and W. W. Li, "Spectra of hypergraphs and applications," J. Number Theory, vol. 60, iss. 1, pp. 1-22, 1996.
@article{FengLi, mrkey = {1405722},
author = {Feng, Keqin and Li, Wen-Ch'ing Winnie},
title = {Spectra of hypergraphs and applications},
journal = {J. Number Theory},
fjournal = {Journal of Number Theory},
volume = {60},
year = {1996},
number = {1},
pages = {1--22},
issn = {0022-314X},
coden = {JNUTA9},
mrclass = {05C50 (05C65 11F99)},
mrnumber = {1405722},
mrreviewer = {A. A. Chernyak},
doi = {10.1006/jnth.1996.0109},
zblnumber = {0874.05041},
} -
[friedman2003relative] J. Friedman, "Relative expanders or weakly relatively Ramanujan graphs," Duke Math. J., vol. 118, iss. 1, pp. 19-35, 2003.
@article{friedman2003relative, mrkey = {1978881},
author = {Friedman, Joel},
title = {Relative expanders or weakly relatively {R}amanujan graphs},
journal = {Duke Math. J.},
fjournal = {Duke Mathematical Journal},
volume = {118},
year = {2003},
number = {1},
pages = {19--35},
issn = {0012-7094},
coden = {DUMJAO},
mrclass = {05C50 (68R10)},
mrnumber = {1978881},
doi = {10.1215/S0012-7094-03-11812-8},
zblnumber = {1035.05058},
} -
[friedman2008] J. Friedman, "A proof of Alon’s second eigenvalue conjecture and related problems," Mem. Amer. Math. Soc., vol. 195, iss. 910, p. viii, 2008.
@article{friedman2008, mrkey = {2437174},
author = {Friedman, Joel},
title = {A proof of {A}lon's second eigenvalue conjecture and related problems},
journal = {Mem. Amer. Math. Soc.},
fjournal = {Memoirs of the American Mathematical Society},
volume = {195},
year = {2008},
number = {910},
pages = {viii+100},
issn = {0065-9266},
coden = {MAMCAU},
isbn = {978-0-8218-4280-5},
mrclass = {05C50 (05C80 05C81 68R10)},
mrnumber = {2437174},
mrreviewer = {Thomas Britz},
doi = {10.1090/memo/0910},
zblnumber = {1177.05070},
} -
[Godsil] C. D. Godsil, "Matchings and walks in graphs," J. Graph Theory, vol. 5, iss. 3, pp. 285-297, 1981.
@article{Godsil, mrkey = {0625070},
author = {Godsil, C. D.},
title = {Matchings and walks in graphs},
journal = {J. Graph Theory},
fjournal = {Journal of Graph Theory},
volume = {5},
year = {1981},
number = {3},
pages = {285--297},
issn = {0364-9024},
coden = {JGTHDO},
mrclass = {05C70 (05C38 60C05)},
mrnumber = {0625070},
mrreviewer = {Charles H. C. Little},
doi = {10.1002/jgt.3190050310},
zblnumber = {0466.05053},
} -
[GodsilGutman] C. D. Godsil and I. Gutman, "On the matching polynomial of a graph," in Algebraic Methods in Graph Theory, Vol. I, II, New York: North-Holland, 1981, vol. 25, pp. 241-249.
@incollection{GodsilGutman, mrkey = {0642044},
author = {Godsil, C. D. and Gutman, I.},
title = {On the matching polynomial of a graph},
booktitle = {Algebraic Methods in Graph Theory, {V}ol. {I},
{II}},
venue = {{S}zeged, 1978},
series = {Colloq. Math. Soc. János Bolyai},
volume = {25},
pages = {241--249},
publisher = {North-Holland},
address = {New York},
year = {1981},
mrclass = {05C70 (33A65)},
mrnumber = {0642044},
mrreviewer = {E. J. Farrell},
zblnumber = {0476.05060},
} -
[GodsilBook] C. D. Godsil, Algebraic Combinatorics, New York: Chapman & Hall, 1993.
@book{GodsilBook, mrkey = {1220704},
author = {Godsil, C. D.},
title = {Algebraic Combinatorics},
series = {Chapman and Hall Math. Series},
publisher = {Chapman \& Hall},
address = {New York},
year = {1993},
pages = {xvi+362},
isbn = {0-412-04131-6},
mrclass = {05-01},
mrnumber = {1220704},
mrreviewer = {Andrew Woldar},
zblnumber = {0784.05001},
} -
[godsilMohar] C. D. Godsil and B. Mohar, "Walk generating functions and spectral measures of infinite graphs," in Proceedings of the Victoria Conference on Combinatorial Matrix Analysis, 1988, pp. 191-206.
@inproceedings{godsilMohar, mrkey = {0960145},
author = {Godsil, C. D. and Mohar, B.},
title = {Walk generating functions and spectral measures of infinite graphs},
booktitle = {Proceedings of the {V}ictoria {C}onference on {C}ombinatorial {M}atrix {A}nalysis},
venue = {{V}ictoria, {BC},
1987)},
series = {Linear Algebra Appl.},
fjournal = {Linear Algebra and its Applications},
volume = {107},
year = {1988},
pages = {191--206},
issn = {0024-3795},
coden = {LAAPAW},
mrclass = {05C50},
mrnumber = {0960145},
mrreviewer = {M. Doob},
doi = {10.1016/0024-3795(88)90245-5},
zblnumber = {0654.05054},
} -
[greenberg] Y. Greenberg, On the spectrum of graphs and their universal covering, 1995.
@misc{greenberg,
author = {Greenberg, Y.},
title = {On the spectrum of graphs and their universal covering},
note = {Ph.D. thesis, Hebrew University},
year = {1995},
} -
[harville2008matrix] D. A. Harville, Matrix Algebra from a Statistician’s Perspective, New York: Springer-Verlag, 2008.
@book{harville2008matrix,
author = {Harville, D. A.},
title = {Matrix Algebra from a Statistician's Perspective},
publisher = {Springer-Verlag},
address = {New York},
year = {2008},
zblnumber = {1142.15001},
} -
[HeilmannLieb] O. J. Heilmann and E. H. Lieb, "Theory of monomer-dimer systems," Comm. Math. Phys., vol. 25, pp. 190-232, 1972.
@article{HeilmannLieb, mrkey = {0297280},
author = {Heilmann, Ole J. and Lieb, Elliott H.},
title = {Theory of monomer-dimer systems},
journal = {Comm. Math. Phys.},
fjournal = {Communications in Mathematical Physics},
volume = {25},
year = {1972},
pages = {190--232},
issn = {0010-3616},
mrclass = {82.05},
mrnumber = {0297280},
doi = {10.1007/BF01877590},
zblnumber = {0228.05131},
} -
[hoory2006expander] S. Hoory, N. Linial, and A. Wigderson, "Expander graphs and their applications," Bull. Amer. Math. Soc., vol. 43, iss. 4, pp. 439-561, 2006.
@article{hoory2006expander, mrkey = {2247919},
author = {Hoory, Shlomo and Linial, Nathan and Wigderson, Avi},
title = {Expander graphs and their applications},
journal = {Bull. Amer. Math. Soc.},
fjournal = {American Mathematical Society. Bulletin. New Series},
volume = {43},
year = {2006},
number = {4},
pages = {439--561},
issn = {0273-0979},
coden = {BAMOAD},
mrclass = {68Q15 (00-02 05C25 05C80 60G50 68Q17 68R10)},
mrnumber = {2247919},
mrreviewer = {Mark R. Jerrum},
doi = {10.1090/S0273-0979-06-01126-8},
zblnumber = {1147.68608},
} -
[jordan1997ramanujan] B. W. Jordan and R. Livné, "Ramanujan local systems on graphs," Topology, vol. 36, iss. 5, pp. 1007-1024, 1997.
@article{jordan1997ramanujan, mrkey = {1445552},
author = {Jordan, Bruce W. and Livn{é},
Ron},
title = {Ramanujan local systems on graphs},
journal = {Topology},
fjournal = {Topology. An International Journal of Mathematics},
volume = {36},
year = {1997},
number = {5},
pages = {1007--1024},
issn = {0040-9383},
coden = {TPLGAF},
mrclass = {05C50 (05C25)},
mrnumber = {1445552},
mrreviewer = {Zhaojun Liang},
doi = {10.1016/S0040-9383(96)00044-4},
zblnumber = {0872.05036},
} -
[LiSole] W. W. Li and P. Solé, "Spectra of regular graphs and hypergraphs and orthogonal polynomials," European J. Combin., vol. 17, iss. 5, pp. 461-477, 1996.
@article{LiSole, mrkey = {1397154},
author = {Li, Wen-Ch'ing Winnie and Sol{é},
Patrick},
title = {Spectra of regular graphs and hypergraphs and orthogonal polynomials},
journal = {European J. Combin.},
fjournal = {European Journal of Combinatorics},
volume = {17},
year = {1996},
number = {5},
pages = {461--477},
issn = {0195-6698},
mrclass = {05C50 (05C65)},
mrnumber = {1397154},
doi = {10.1006/eujc.1996.0040},
zblnumber = {0864.05072},
} -
[linial2010word] N. Linial and D. Puder, "Word maps and spectra of random graph lifts," Random Structures Algorithms, vol. 37, iss. 1, pp. 100-135, 2010.
@article{linial2010word, mrkey = {2674623},
author = {Linial, Nati and Puder, Doron},
title = {Word maps and spectra of random graph lifts},
journal = {Random Structures Algorithms},
fjournal = {Random Structures \& Algorithms},
volume = {37},
year = {2010},
number = {1},
pages = {100--135},
issn = {1042-9832},
mrclass = {60C05 (68Q70)},
mrnumber = {2674623},
doi = {10.1002/rsa.20304},
zblnumber = {1242.60011},
} -
[linial2005random] N. Linial and E. Rozenman, "Random lifts of graphs: perfect matchings," Combinatorica, vol. 25, iss. 4, pp. 407-424, 2005.
@article{linial2005random, mrkey = {2143247},
author = {Linial, Nathan and Rozenman, Eyal},
title = {Random lifts of graphs: perfect matchings},
journal = {Combinatorica},
fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
volume = {25},
year = {2005},
number = {4},
pages = {407--424},
issn = {0209-9683},
mrclass = {05C70 (05C80)},
mrnumber = {2143247},
mrreviewer = {Deryk Osthus},
doi = {10.1007/s00493-005-0024-8},
zblnumber = {1091.05063},
} -
[lubetzky2011spectra] E. Lubetzky, B. Sudakov, and V. Vu, "Spectra of lifted Ramanujan graphs," Adv. Math., vol. 227, iss. 4, pp. 1612-1645, 2011.
@article{lubetzky2011spectra, mrkey = {2799807},
author = {Lubetzky, Eyal and Sudakov, Benny and Vu, Van},
title = {Spectra of lifted {R}amanujan graphs},
journal = {Adv. Math.},
fjournal = {Advances in Mathematics},
volume = {227},
year = {2011},
number = {4},
pages = {1612--1645},
issn = {0001-8708},
coden = {ADMTA4},
mrclass = {05C50 (05C75 05C80 68R10)},
mrnumber = {2799807},
mrreviewer = {Aleksandar Ili{ć}},
doi = {10.1016/j.aim.2011.03.016},
zblnumber = {1222.05168},
} -
[LPS] A. Lubotzky, R. Phillips, and P. Sarnak, "Ramanujan graphs," Combinatorica, vol. 8, iss. 3, pp. 261-277, 1988.
@article{LPS, mrkey = {0963118},
author = {Lubotzky, A. and Phillips, R. and Sarnak, P.},
title = {Ramanujan graphs},
journal = {Combinatorica},
fjournal = {Combinatorica. An International Journal of the János Bolyai Mathematical Society},
volume = {8},
year = {1988},
number = {3},
pages = {261--277},
issn = {0209-9683},
coden = {COMBDI},
mrclass = {05C75 (05C25 05C50)},
mrnumber = {0963118},
mrreviewer = {Dave Witte Morris},
doi = {10.1007/BF02126799},
zblnumber = {0661.05035},
} -
[LubotzkyBook] A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Birkhäuser, Basel, 1994, vol. 125.
@book{LubotzkyBook, mrkey = {1308046},
author = {Lubotzky, Alexander},
title = {Discrete Groups, Expanding Graphs and Invariant Measures},
series = {Progr. Math.},
volume = {125},
note = {with an appendix by Jonathan D. Rogawski},
publisher = {Birkhäuser, Basel},
year = {1994},
pages = {xii+195},
isbn = {3-7643-5075-X},
mrclass = {22E40 (05C25 11F70 28C10 43A07)},
mrnumber = {1308046},
mrreviewer = {Wolfgang Woess},
doi = {10.1007/978-3-0346-0332-4},
zblnumber = {0826.22012},
} -
[lubotzky1998not] A. Lubotzky and T. Nagnibeda, "Not every uniform tree covers Ramanujan graphs," J. Combin. Theory Ser. B, vol. 74, iss. 2, pp. 202-212, 1998.
@article{lubotzky1998not, mrkey = {1654133},
author = {Lubotzky, Alexander and Nagnibeda, Tatiana},
title = {Not every uniform tree covers {R}amanujan graphs},
journal = {J. Combin. Theory Ser. B},
fjournal = {Journal of Combinatorial Theory. Series B},
volume = {74},
year = {1998},
number = {2},
pages = {202--212},
issn = {0095-8956},
coden = {JCBTB8},
mrclass = {05C05 (05C70)},
mrnumber = {1654133},
doi = {10.1006/jctb.1998.1843},
zblnumber = {1024.05021},
} -
[IF2] A. Marcus, D. A. Spielman, and N. Srivastava, "Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem," Ann. of Math., vol. 182, pp. 327-350, 2015.
@article{IF2,
author = {Marcus, A. and Spielman, D. A. and Srivastava, N.},
title = {Interlacing families {II}: Mixed characteristic polynomials and the {Kadison-Singer} problem},
journal = {Ann. of Math.},
year = {2015},
volume = {182},
pages = {327--350},
doi = {10.4007/annals/2015.182.1.8},
} -
[Margulis] G. A. Margulis, "Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators," Problemy Peredachi Informatsii, vol. 24, iss. 1, pp. 51-60, 1988.
@article{Margulis, mrkey = {0939574},
author = {Margulis, G. A.},
title = {Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators},
journal = {Problemy Peredachi Informatsii},
fjournal = {Akademiya Nauk SSSR. Institut Problem Peredachi Informatsii Akademii Nauk SSSR. Problemy Peredachi Informatsii},
volume = {24},
year = {1988},
number = {1},
pages = {51--60},
issn = {0555-2923},
mrclass = {68R10 (05C99 94A15)},
mrnumber = {0939574},
mrreviewer = {Mirko K{\v{r}}iv{á}nek},
zblnumber = {0708.05030},
} -
[Morgenstern] M. Morgenstern, "Existence and explicit constructions of $q+1$ regular Ramanujan graphs for every prime power $q$," J. Combin. Theory Ser. B, vol. 62, iss. 1, pp. 44-62, 1994.
@article{Morgenstern, mrkey = {1290630},
author = {Morgenstern, Moshe},
title = {Existence and explicit constructions of {$q+1$} regular {R}amanujan graphs for every prime power {$q$}},
journal = {J. Combin. Theory Ser. B},
fjournal = {Journal of Combinatorial Theory. Series B},
volume = {62},
year = {1994},
number = {1},
pages = {44--62},
issn = {0095-8956},
coden = {JCBTB8},
mrclass = {05C35 (05C25)},
mrnumber = {1290630},
mrreviewer = {Marcus du Sautoy},
doi = {10.1006/jctb.1994.1054},
zblnumber = {0814.68098},
} -
[nilli] A. Nilli, "On the second eigenvalue of a graph," Discrete Math., vol. 91, iss. 2, pp. 207-210, 1991.
@article{nilli, mrkey = {1124768},
author = {Nilli, A.},
title = {On the second eigenvalue of a graph},
journal = {Discrete Math.},
fjournal = {Discrete Mathematics},
volume = {91},
year = {1991},
number = {2},
pages = {207--210},
issn = {0012-365X},
coden = {DSMHA4},
mrclass = {05C50},
mrnumber = {1124768},
mrreviewer = {Wan Di Wei},
doi = {10.1016/0012-365X(91)90112-F},
zblnumber = {0771.05064},
} -
[pemantle] R. Pemantle, "Hyperbolicity and stable polynomials in combinatorics and probability," in Current Developments in Mathematics, 2011, Somerville, MA: Int. Press, 2012, pp. 57-123.
@incollection{pemantle, mrkey = {3098077},
author = {Pemantle, Robin},
title = {Hyperbolicity and stable polynomials in combinatorics and probability},
booktitle = {Current Developments in Mathematics, 2011},
pages = {57--123},
publisher = {Int. Press},
address = {Somerville, MA},
year = {2012},
mrclass = {62H20 (05A15 26C10 30C15)},
mrnumber = {3098077},
mrreviewer = {Marius R{\u{a}}dulescu},
} -
[pizer] A. K. Pizer, "Ramanujan graphs and Hecke operators," Bull. Amer. Math. Soc., vol. 23, iss. 1, pp. 127-137, 1990.
@article{pizer, mrkey = {1027904},
author = {Pizer, Arnold K.},
title = {Ramanujan graphs and {H}ecke operators},
journal = {Bull. Amer. Math. Soc.},
fjournal = {American Mathematical Society. Bulletin. New Series},
volume = {23},
year = {1990},
number = {1},
pages = {127--137},
issn = {0273-0979},
coden = {BAMOAD},
mrclass = {11F11 (05C50 11F12 11F25)},
mrnumber = {1027904},
mrreviewer = {T. C. Vasudevan},
doi = {10.1090/S0273-0979-1990-15918-X},
zblnumber = {0752.05035},
} -
[puder2012expansion] D. Puder, Expansion of random graphs: New proofs, new results, 2012.
@misc{puder2012expansion,
author = {Puder, D.},
title = {Expansion of random graphs: {N}ew proofs, new results},
arxiv = {1212.5216},
year = {2012},
} -
[FuncAnal] M. Reed and B. Simon, Methods of Modern Mathematical Physics. I. Functional Aanalysis, Second ed., Academic Press [Harcourt Brace Jovanovich, Publishers], 1980.
@book{FuncAnal, mrkey = {0751959},
author = {Reed, Michael and Simon, Barry},
title = {{M}ethods of {M}odern {M}athematical {P}hysics. {I}. {F}unctional {A}analysis},
edition = {Second},
publisher = {Academic Press [Harcourt Brace Jovanovich, Publishers]},
addres = {New York},
year = {1980},
pages = {xv+400},
isbn = {0-12-585050-6},
mrclass = {46-01 (47-01)},
mrnumber = {0751959},
zblnumber = {0459.46001},
} -
[valiantPermanent] L. G. Valiant, "The complexity of computing the permanent," Theoret. Comput. Sci., vol. 8, iss. 2, pp. 189-201, 1979.
@article{valiantPermanent, mrkey = {0526203},
author = {Valiant, L. G.},
title = {The complexity of computing the permanent},
journal = {Theoret. Comput. Sci.},
fjournal = {Theoretical Computer Science},
volume = {8},
year = {1979},
number = {2},
pages = {189--201},
issn = {0304-3975},
coden = {TCSDI},
mrclass = {68C25 (15A15)},
mrnumber = {0526203},
doi = {10.1016/0304-3975(79)90044-6},
zblnumber = {0415.68008},
} -
[wagner] D. G. Wagner, "Multivariate stable polynomials: theory and applications," Bull. Amer. Math. Soc., vol. 48, iss. 1, pp. 53-84, 2011.
@article{wagner, mrkey = {2738906},
author = {Wagner, David G.},
title = {Multivariate stable polynomials: theory and applications},
journal = {Bull. Amer. Math. Soc.},
fjournal = {American Mathematical Society. Bulletin. New Series},
volume = {48},
year = {2011},
number = {1},
pages = {53--84},
issn = {0273-0979},
coden = {BAMOAD},
mrclass = {32A60 (05A20 05B35 15A45)},
mrnumber = {2738906},
doi = {10.1090/S0273-0979-2010-01321-5},
zblnumber = {1207.32006},
}
Full Article