×
Marcus, Adam W.; Spielman, Daniel A.; Srivastava, Nikhil

Interlacing families. I: Bipartite Ramanujan graphs of all degrees. (English) Zbl 1316.05066

Ann. Math. (2) 182, No. 1, 307-325 (2015).
Summary: 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.”

Cited in 12 Reviews
Cited in 113 Documents

MathOverflow Questions:

Explicit constructions of Ramanujan graphs

MSC:

05C31 Graph polynomials

Keywords:

lifts of graphs; matching polynomials of graphs; Ramanujan graphs
PDF BibTeX XML Cite
\textit{A. W. Marcus} et al., Ann. Math. (2) 182, No. 1, 307--325 (2015; Zbl 1316.05066)
Full Text: DOI arXiv

References:

[1] L. Addario-Berry and S. Griffiths, The spectrum of random lifts, 2010.
[2] A. Amit and N. Linial, ”Random lifts of graphs: edge expansion,” Combin. Probab. Comput., vol. 15, iss. 3, pp. 317-332, 2006. · Zbl 1095.05034
[3] 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. · Zbl 0993.05071
[4] Y. Bilu and N. Linial, ”Lifts, discrepancy and nearly optimal spectral gap,” Combinatorica, vol. 26, iss. 5, pp. 495-519, 2006. · Zbl 1121.05054
[5] 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. · Zbl 1151.15013
[6] 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. · Zbl 1196.47028
[7] P. Chiu, ”Cubic Ramanujan graphs,” Combinatorica, vol. 12, iss. 3, pp. 275-285, 1992. · Zbl 0770.05062
[8] 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. · Zbl 1119.05075
[9] 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. · Zbl 1109.05068
[10] 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. · Zbl 0772.12002
[11] H. J. Fell, ”On the zeros of convex combinations of polynomials,” Pacific J. Math., vol. 89, iss. 1, pp. 43-50, 1980. · Zbl 0416.30005
[12] K. Feng and W. W. Li, ”Spectra of hypergraphs and applications,” J. Number Theory, vol. 60, iss. 1, pp. 1-22, 1996. · Zbl 0874.05041
[13] J. Friedman, ”Relative expanders or weakly relatively Ramanujan graphs,” Duke Math. J., vol. 118, iss. 1, pp. 19-35, 2003. · Zbl 1035.05058
[14] J. Friedman, ”A proof of Alon’s second eigenvalue conjecture and related problems,” Mem. Amer. Math. Soc., vol. 195, iss. 910, p. viii, 2008. · Zbl 1177.05070
[15] C. D. Godsil, ”Matchings and walks in graphs,” J. Graph Theory, vol. 5, iss. 3, pp. 285-297, 1981. · Zbl 0466.05053
[16] 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. · Zbl 0476.05060
[17] C. D. Godsil, Algebraic Combinatorics, New York: Chapman & Hall, 1993. · Zbl 0784.05001
[18] 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. · Zbl 0654.05054
[19] Y. Greenberg, On the spectrum of graphs and their universal covering, 1995.
[20] D. A. Harville, Matrix Algebra from a Statistician’s Perspective, New York: Springer-Verlag, 2008. · Zbl 1142.15001
[21] O. J. Heilmann and E. H. Lieb, ”Theory of monomer-dimer systems,” Comm. Math. Phys., vol. 25, pp. 190-232, 1972. · Zbl 0228.05131
[22] S. Hoory, N. Linial, and A. Wigderson, ”Expander graphs and their applications,” Bull. Amer. Math. Soc., vol. 43, iss. 4, pp. 439-561, 2006. · Zbl 1147.68608
[23] B. W. Jordan and R. Livné, ”Ramanujan local systems on graphs,” Topology, vol. 36, iss. 5, pp. 1007-1024, 1997. · Zbl 0872.05036
[24] 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. · Zbl 0864.05072
[25] N. Linial and D. Puder, ”Word maps and spectra of random graph lifts,” Random Structures Algorithms, vol. 37, iss. 1, pp. 100-135, 2010. · Zbl 1242.60011
[26] N. Linial and E. Rozenman, ”Random lifts of graphs: perfect matchings,” Combinatorica, vol. 25, iss. 4, pp. 407-424, 2005. · Zbl 1091.05063
[27] E. Lubetzky, B. Sudakov, and V. Vu, ”Spectra of lifted Ramanujan graphs,” Adv. Math., vol. 227, iss. 4, pp. 1612-1645, 2011. · Zbl 1222.05168
[28] A. Lubotzky, R. Phillips, and P. Sarnak, ”Ramanujan graphs,” Combinatorica, vol. 8, iss. 3, pp. 261-277, 1988. · Zbl 0661.05035
[29] A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Birkhäuser, Basel, 1994, vol. 125. · Zbl 0826.22012
[30] 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. · Zbl 1024.05021
[31] 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. · Zbl 1332.46056
[32] 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. · Zbl 0708.05030
[33] 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. · Zbl 0814.68098
[34] A. Nilli, ”On the second eigenvalue of a graph,” Discrete Math., vol. 91, iss. 2, pp. 207-210, 1991. · Zbl 0771.05064
[35] R. Pemantle, ”Hyperbolicity and stable polynomials in combinatorics and probability,” in Current Developments in Mathematics, 2011, Somerville, MA: Int. Press, 2012, pp. 57-123. · Zbl 1316.62078
[36] A. K. Pizer, ”Ramanujan graphs and Hecke operators,” Bull. Amer. Math. Soc., vol. 23, iss. 1, pp. 127-137, 1990. · Zbl 0752.05035
[37] D. Puder, Expansion of random graphs: New proofs, new results, 2012. · Zbl 1320.05115
[38] M. Reed and B. Simon, Methods of Modern Mathematical Physics. I. Functional Aanalysis, Second ed., Academic Press [Harcourt Brace Jovanovich, Publishers], 1980. · Zbl 0459.46001
[39] L. G. Valiant, ”The complexity of computing the permanent,” Theoret. Comput. Sci., vol. 8, iss. 2, pp. 189-201, 1979. · Zbl 0415.68008
[40] D. G. Wagner, ”Multivariate stable polynomials: theory and applications,” Bull. Amer. Math. Soc., vol. 48, iss. 1, pp. 53-84, 2011. · Zbl 1207.32006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.