Eigenvalues of random lifts and polynomials of random permutation matrices

Abstract

Let $(\sigma _{1}, \ldots , \sigma _d)$ be a finite sequence of independent random permutations, chosen uniformly either among all permutations or among all matchings on $n$ points. We show that, in probability, as $n\to \infty $, these permutations viewed as operators on the $n-1$ dimensional vector space $\{(x_1,\ldots , x_n) \in \mathbb {C}^n, \sum x_i=0\}$, are asymptotically strongly free. Our proof relies on the development of a matrix version of the non-backtracking operator theory and a refined trace method.

As a byproduct, we show that the non-trivial eigenvalues of random $n$-lifts of a fixed based graphs approximately achieve the Alon-Boppana bound with high probability in the large $n$ limit. This result generalizes Friedman’s Theorem stating that with high probability, the Schreier graph generated by a finite number of independent random permutations is close to Ramanujan.

Finally, we extend our results to tensor products of random permutation matrices. This extension is especially relevant in the context of quantum expanders.

  • [AB-S] L. Addario-Berry and S. Griffiths, The spectrum of random lifts, 2010.
    @MISC{AB-S,
      author = {Addario-Berry, L. and Griffiths, S.},
      title = {The spectrum of random lifts },
      arxiv = {1012.4097},
      year = {2010},
      zblnumber = {},
      }
  • [MR0442698] Go to document C. A. Akemann and P. A. Ostrand, "Computing norms in group $C\sp*$-algebras," Amer. J. Math., vol. 98, iss. 4, pp. 1015-1047, 1976.
    @ARTICLE{MR0442698,
      author = {Akemann, Charles A. and Ostrand, Phillip A.},
      title = {Computing norms in group {$C\sp*$}-algebras},
      journal = {Amer. J. Math.},
      fjournal = {American Journal of Mathematics},
      volume = {98},
      year = {1976},
      number = {4},
      pages = {1015--1047},
      issn = {0002-9327},
      mrclass = {46L05 (22D25)},
      mrnumber = {0442698},
      mrreviewer = {R. C. Busby},
      doi = {10.2307/2374039},
      url = {https://doi.org/10.2307/2374039},
      zblnumber = {0342.22008},
      }
  • [MR2354165] Go to document D. Aldous and R. Lyons, "Processes on unimodular random networks," Electron. J. Probab., vol. 12, p. no. 54, 1454-1508, 2007.
    @ARTICLE{MR2354165,
      author = {Aldous, David and Lyons, Russell},
      title = {Processes on unimodular random networks},
      journal = {Electron. J. Probab.},
      fjournal = {Electronic Journal of Probability},
      volume = {12},
      year = {2007},
      pages = {no. 54, 1454--1508},
      issn = {1083-6489},
      mrclass = {60C05 (05C80 60G50)},
      mrnumber = {2354165},
      mrreviewer = {Jean-François Delmas},
      doi = {10.1214/EJP.v12-463},
      url = {https://doi.org/10.1214/EJP.v12-463},
      zblnumber = {1131.60003},
      }
  • [MR1883559] Go to document A. Amit and N. Linial, "Random graph coverings. I. General theory and graph connectivity," Combinatorica, vol. 22, iss. 1, pp. 1-18, 2002.
    @ARTICLE{MR1883559,
      author = {Amit, Alon and Linial, Nathan},
      title = {Random graph coverings. {I}. {G}eneral theory and graph connectivity},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      volume = {22},
      year = {2002},
      number = {1},
      pages = {1--18},
      issn = {0209-9683},
      mrclass = {05C80 (05C10 05C40)},
      mrnumber = {1883559},
      mrreviewer = {Lauren\c{t}iu Modan},
      doi = {10.1007/s004930200000},
      url = {https://doi.org/10.1007/s004930200000},
      zblnumber = {0996.05105},
      }
  • [MR2216470] Go to document A. Amit and N. Linial, "Random lifts of graphs: edge expansion," Combin. Probab. Comput., vol. 15, iss. 3, pp. 317-332, 2006.
    @ARTICLE{MR2216470,
      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},
      url = {https://doi.org/10.1017/S0963548305007273},
      zblnumber = {1095.05034},
      }
  • [MR3649482] Go to document N. Anantharaman, "Quantum ergodicity on regular graphs," Comm. Math. Phys., vol. 353, iss. 2, pp. 633-690, 2017.
    @ARTICLE{MR3649482,
      author = {Anantharaman, Nalini},
      title = {Quantum ergodicity on regular graphs},
      journal = {Comm. Math. Phys.},
      fjournal = {Communications in Mathematical Physics},
      volume = {353},
      year = {2017},
      number = {2},
      pages = {633--690},
      issn = {0010-3616},
      mrclass = {58J51 (05C50 60G50)},
      mrnumber = {3649482},
      mrreviewer = {Dubi Kelmer},
      doi = {10.1007/s00220-017-2879-9},
      url = {https://doi.org/10.1007/s00220-017-2879-9},
      zblnumber = {1368.58015},
      }
  • [MR3098069] Go to document G. W. Anderson, "Convergence of the largest singular value of a polynomial in independent Wigner matrices," Ann. Probab., vol. 41, iss. 3B, pp. 2103-2181, 2013.
    @ARTICLE{MR3098069,
      author = {Anderson, Greg W.},
      title = {Convergence of the largest singular value of a polynomial in independent {W}igner matrices},
      journal = {Ann. Probab.},
      fjournal = {The Annals of Probability},
      volume = {41},
      year = {2013},
      number = {3B},
      pages = {2103--2181},
      issn = {0091-1798},
      mrclass = {60B20 (15B52)},
      mrnumber = {3098069},
      mrreviewer = {Nizar Demni},
      doi = {10.1214/11-AOP739},
      url = {https://doi.org/10.1214/11-AOP739},
      zblnumber = {1282.60007},
      }
  • [MR3792625] C. Bordenave, "Spectrum of random graphs," in Advanced Topics in Random Matrices, Soc. Math. France, Paris, 2017, vol. 53, pp. 91-150.
    @INCOLLECTION{MR3792625,
      author = {Bordenave, Charles},
      title = {Spectrum of random graphs},
      booktitle = {Advanced {T}opics in {R}andom {M}atrices},
      series = {Panor. Synthèses},
      volume = {53},
      pages = {91--150},
      publisher = {Soc. Math. France, Paris},
      year = {2017},
      mrclass = {60B20 (05C80 15B52)},
      mrnumber = {3792625},
      zblnumber = {1395.05149},
      }
  • [bordenaveCAT] C. Bordenave, A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts.
    @MISC{bordenaveCAT,
      author = {Bordenave, Charles},
      title = {A new proof of {F}riedman{'}s second eigenvalue theorem and its extension to random lifts},
      note = {{\em Ann. {S}ci. {É}c. {N}orm. {S}upér.},
      to appear},
      sortyear={2122},
      }
  • [BLM] Go to document C. Bordenave, M. Lelarge, and L. Massoulié, "Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs," Ann. Probab., vol. 46, iss. 1, pp. 1-71, 2018.
    @ARTICLE{BLM,
      author = {Bordenave, Charles and Lelarge, Marc and Massoulié,
      Laurent},
      title = {Nonbacktracking spectrum of random graphs: community detection and nonregular {R}amanujan graphs},
      journal = {Ann. Probab.},
      fjournal = {The Annals of Probability},
      volume = {46},
      year = {2018},
      number = {1},
      pages = {1--71},
      issn = {0091-1798},
      mrclass = {05C80 (60B20 60J85 62M15)},
      mrnumber = {3758726},
      mrreviewer = {D. Yogeshwaran},
      doi = {10.1214/16-AOP1142},
      url = {https://doi.org/10.1214/16-AOP1142},
      zblnumber = {1386.05174},
      }
  • [MR1476122] Go to document A. Buchholz, "Norm of convolution by operator-valued functions on free groups," Proc. Amer. Math. Soc., vol. 127, iss. 6, pp. 1671-1682, 1999.
    @ARTICLE{MR1476122,
      author = {Buchholz, Artur},
      title = {Norm of convolution by operator-valued functions on free groups},
      journal = {Proc. Amer. Math. Soc.},
      fjournal = {Proceedings of the American Mathematical Society},
      volume = {127},
      year = {1999},
      number = {6},
      pages = {1671--1682},
      issn = {0002-9939},
      mrclass = {43A30 (43A65)},
      mrnumber = {1476122},
      mrreviewer = {George A. Willis},
      doi = {10.1090/S0002-9939-99-04660-2},
      url = {https://doi.org/10.1090/S0002-9939-99-04660-2},
      zblnumber = {0916.43002},
      }
  • [CECCHERINISILBERSTEIN2004735] Go to document T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, "Weighted expanders and the anisotropic Alon-Boppana theorem," European J. Combin., vol. 25, iss. 5, pp. 735-744, 2004.
    @ARTICLE{CECCHERINISILBERSTEIN2004735,
      author = {Ceccherini-Silberstein, Tullio and Scarabotti, Fabio and Tolli, Filippo},
      title = {Weighted expanders and the anisotropic {A}lon-{B}oppana theorem},
      journal = {European J. Combin.},
      fjournal = {European Journal of Combinatorics},
      volume = {25},
      year = {2004},
      number = {5},
      pages = {735--744},
      issn = {0195-6698},
      mrclass = {05C50 (60G50)},
      mrnumber = {2061396},
      mrreviewer = {Mark R. Jerrum},
      doi = {10.1016/j.ejc.2003.10.008},
      url = {https://doi.org/10.1016/j.ejc.2003.10.008},
      zblnumber = {1048.05057},
      }
  • [MR3573218] Go to document B. Collins and P. Y. Gaudreau Lamarre, "$\ast$-freeness in finite tensor products," Adv. in Appl. Math., vol. 83, pp. 47-80, 2017.
    @ARTICLE{MR3573218,
      author = {Collins, Benoit and Gaudreau Lamarre, Pierre Yves},
      title = {{$\ast$}-freeness in finite tensor products},
      journal = {Adv. in Appl. Math.},
      fjournal = {Advances in Applied Mathematics},
      volume = {83},
      year = {2017},
      pages = {47--80},
      issn = {0196-8858},
      mrclass = {46L54 (20C07 46L06 46L53)},
      mrnumber = {3573218},
      mrreviewer = {Florent Benaych-Georges},
      doi = {10.1016/j.aam.2016.09.002},
      url = {https://doi.org/10.1016/j.aam.2016.09.002},
      zblnumber = {1369.46059},
      }
  • [MR3205602] Go to document B. Collins and C. Male, "The strong asymptotic freeness of Haar and deterministic matrices," Ann. Sci. Éc. Norm. Supér. (4), vol. 47, iss. 1, pp. 147-163, 2014.
    @ARTICLE{MR3205602,
      author = {Collins, Beno\^ıt and Male, Camille},
      title = {The strong asymptotic freeness of {H}aar and deterministic matrices},
      journal = {Ann. Sci. \'{E}c. Norm. Supér. (4)},
      fjournal = {Annales Scientifiques de l'\'{E}cole Normale Supérieure. Quatrième Série},
      volume = {47},
      year = {2014},
      number = {1},
      pages = {147--163},
      issn = {0012-9593},
      mrclass = {60B20 (46L54)},
      mrnumber = {3205602},
      doi = {10.24033/asens.2211},
      url = {https://doi.org/10.24033/asens.2211},
      zblnumber = {1303.15043},
      }
  • [MR787404] Go to document K. Deimling, Nonlinear Functional Analysis, Springer-Verlag, Berlin, 1985.
    @BOOK{MR787404,
      author = {Deimling, Klaus},
      title = {Nonlinear {F}unctional {A}nalysis},
      publisher = {Springer-Verlag, Berlin},
      year = {1985},
      pages = {xiv+450},
      isbn = {3-540-13928-1},
      mrclass = {47-01 (47Hxx 55M25 58-01 58Cxx)},
      mrnumber = {0787404},
      mrreviewer = {Joachim Naumann},
      doi = {10.1007/978-3-662-00547-7},
      url = {https://doi.org/10.1007/978-3-662-00547-7},
      zblnumber = {1257.47059},
      }
  • [MR1219707] Go to document A. Figà-Talamanca and T. Steger, "Harmonic analysis for anisotropic random walks on homogeneous trees," Mem. Amer. Math. Soc., vol. 110, iss. 531, p. xii, 1994.
    @ARTICLE{MR1219707,
      author = {Figà-Talamanca, Alessandro and Steger, Tim},
      title = {Harmonic analysis for anisotropic random walks on homogeneous trees},
      journal = {Mem. Amer. Math. Soc.},
      fjournal = {Memoirs of the American Mathematical Society},
      volume = {110},
      year = {1994},
      number = {531},
      pages = {xii+68},
      issn = {0065-9266},
      mrclass = {22D10 (20E08 43A65 60B15)},
      mrnumber = {1219707},
      mrreviewer = {Wolfgang Woess},
      doi = {10.1090/memo/0531},
      url = {https://doi.org/10.1090/memo/0531},
      zblnumber = {0836.43019},
      }
  • [MR1978881] Go to document J. Friedman, "Relative expanders or weakly relatively Ramanujan graphs," Duke Math. J., vol. 118, iss. 1, pp. 19-35, 2003.
    @ARTICLE{MR1978881,
      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},
      mrclass = {05C50 (68R10)},
      mrnumber = {1978881},
      doi = {10.1215/S0012-7094-03-11812-8},
      url = {https://doi.org/10.1215/S0012-7094-03-11812-8},
      zblnumber = {1035.05058},
      }
  • [MR2437174] Go to document 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{MR2437174,
      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},
      isbn = {978-0-8218-4280-5},
      mrclass = {05C50 (05C80 05C81 68R10)},
      mrnumber = {2437174},
      mrreviewer = {Thomas Britz},
      doi = {10.1090/memo/0910},
      url = {https://doi.org/10.1090/memo/0910},
      zblnumber = {1177.05070},
      }
  • [Friedman1996] Go to document J. Friedman, A. Joux, Y. Roichman, J. Stern, and J. P. Tillich, "The action of a few random permutations on $r$-tuples and an application to cryptography," in STACS 96, Springer-Verlag, Berlin, 1996, vol. 1046, pp. 375-386.
    @INCOLLECTION{Friedman1996,
      author = {Friedman, Joel and Joux, A. and Roichman, Y. and Stern, J. and Tillich, J. P.},
      title = {The action of a few random permutations on $r$-tuples and an application to cryptography},
      booktitle = {S{TACS} 96},
      venue={{G}renoble, 1996},
      series = {Lecture Notes in Comput. Sci.},
      volume = {1046},
      pages = {375--386},
      publisher = {Springer-Verlag, Berlin},
      year = {1996},
      zblnumber = {1380.94089},
      mrnumber = {1462111},
      doi = {10.1007/3-540-60922-9_31},
      url = {https://doi.org/10.1007/3-540-60922-9_31},
      }
  • [FrKo] J. Friedman and D. -E. Kohler, The relativized second eigenvalue conjecture of alon, 2014.
    @MISC{FrKo,
      author = {Friedman, Joel and Kohler, D.-E.},
      title = {The relativized second eigenvalue conjecture of alon},
      arxiv = {1403.3462},
      year = {2014},
      zblnumber = {},
      }
  • [MR637828] Go to document Z. Füredi and J. Komlós, "The eigenvalues of random symmetric matrices," Combinatorica, vol. 1, iss. 3, pp. 233-241, 1981.
    @ARTICLE{MR637828,
      author = {Füredi, Z. and Komlós, J.},
      title = {The eigenvalues of random symmetric matrices},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society},
      volume = {1},
      year = {1981},
      number = {3},
      pages = {233--241},
      issn = {0209-9683},
      mrclass = {15A18 (05C50 15A52 60F99)},
      mrnumber = {0637828},
      mrreviewer = {Abbas A. El Gamal},
      doi = {10.1007/BF02579329},
      url = {https://doi.org/10.1007/BF02579329},
      zblnumber = {0494.15010},
      }
  • [greenberg] Y. Greenberg, Spectra of graphs and their covering trees, 1995.
    @MISC{greenberg,
      author = {Greenberg, Y.},
      title = {Spectra of graphs and their covering trees},
      note = {Ph.D. thesis, Hebrew University of Jerusalem},
      year = {1995},
      zblnumber = {},
      }
  • [MR0339722] Go to document L. Gross, "Existence and uniqueness of physical ground states," J. Functional Analysis, vol. 10, pp. 52-109, 1972.
    @ARTICLE{MR0339722,
      author = {Gross, Leonard},
      title = {Existence and uniqueness of physical ground states},
      journal = {J. Functional Analysis},
      volume = {10},
      year = {1972},
      pages = {52--109},
      mrclass = {81.47},
      mrnumber = {0339722},
      mrreviewer = {J. Glimm},
      doi = {10.1016/0022-1236(72)90057-2},
      url = {https://doi.org/10.1016/0022-1236(72)90057-2},
      zblnumber = {0237.47012},
      }
  • [MR2183281] Go to document U. Haagerup and S. Thorbjørnsen, "A new application of random matrices: ${ Ext}(C^*_{ red}(F_2))$ is not a group," Ann. of Math. (2), vol. 162, iss. 2, pp. 711-775, 2005.
    @ARTICLE{MR2183281,
      author = {Haagerup, Uffe and Thorbjørnsen, Steen},
      title = {A new application of random matrices: {${\rm Ext}(C^*_{\rm red}(F_2))$} is not a group},
      journal = {Ann. of Math. (2)},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {162},
      year = {2005},
      number = {2},
      pages = {711--775},
      issn = {0003-486X},
      mrclass = {46L54 (15A52 46L35)},
      mrnumber = {2183281},
      mrreviewer = {Beno\^ıt Collins},
      doi = {10.4007/annals.2005.162.711},
      url = {https://doi.org/10.4007/annals.2005.162.711},
      zblnumber = {1103.46032},
      }
  • [MR2486279] Go to document M. B. Hastings, "Random unitaries give quantum expanders," Phys. Rev. A (3), vol. 76, iss. 3, p. 032315, 2007.
    @ARTICLE{MR2486279,
      author = {Hastings, M. B.},
      title = {Random unitaries give quantum expanders},
      journal = {Phys. Rev. A (3)},
      fjournal = {Physical Review. A. Third Series},
      volume = {76},
      year = {2007},
      number = {3},
      pages = {032315, 11},
      issn = {1050-2947},
      mrclass = {81S99 (81P99)},
      mrnumber = {2486279},
      doi = {10.1103/PhysRevA.76.032315},
      url = {https://doi.org/10.1103/PhysRevA.76.032315},
      zblnumber = {},
      }
  • [Hastings:2009:CQT:2011781.2011790] Go to document M. B. Hastings and A. W. Harrow, "Classical and quantum tensor product expanders," Quantum Inf. Comput., vol. 9, iss. 3-4, pp. 336-360, 2009.
    @ARTICLE{Hastings:2009:CQT:2011781.2011790,
      author = {Hastings, M. B. and Harrow, A. W.},
      title = {Classical and quantum tensor product expanders},
      journal = {Quantum Inf. Comput.},
      fjournal = {Quantum Information \& Computation},
      volume = {9},
      year = {2009},
      number = {3-4},
      pages = {336--360},
      issn = {1533-7146},
      mrclass = {81P68 (81P16)},
      mrnumber = {2553116},
      mrreviewer = {Robin Hudson},
      zblnumber = {1171.81329},
      url = {http://www.rintonpress.com/xxqic9/qic-9-34/0336-0360.pdf},
      }
  • [MR0038008] M. G. Kreuin and M. A. Rutman, "Linear operators leaving invariant a cone in a Banach space," Amer. Math. Soc. Translation, vol. 1950, iss. 26, p. 128, 1950.
    @ARTICLE{MR0038008,
      author = {Kreĭn, M. G. and Rutman, M. A.},
      title = {Linear operators leaving invariant a cone in a {B}anach space},
      journal = {Amer. Math. Soc. Translation},
      fjournal = {American Mathematical Society Translations},
      note = {Translated from Usp. Mat. Nauk (N.S.) {\bf 3},
      no. 1(23), 3--95 (1948)},
      volume = {1950},
      year = {1950},
      number = {26},
      pages = {128},
      issn = {0065-9290},
      mrclass = {46.3X},
      mrnumber = {0038008},
      zblnumber = {0030.12902},
      }
  • [MR1738412] Go to document F. Lehner, "Computing norms of free operators with matrix coefficients," Amer. J. Math., vol. 121, iss. 3, pp. 453-486, 1999.
    @ARTICLE{MR1738412,
      author = {Lehner, Franz},
      title = {Computing norms of free operators with matrix coefficients},
      journal = {Amer. J. Math.},
      fjournal = {American Journal of Mathematics},
      volume = {121},
      year = {1999},
      number = {3},
      pages = {453--486},
      issn = {0002-9327},
      mrclass = {46L54 (22D25)},
      mrnumber = {1738412},
      mrreviewer = {Ken Dykema},
      doi = {10.1353/ajm.1999.0022},
      url = {https://doi.org/10.1353/ajm.1999.0022},
      zblnumber = {0929.22004},
      }
  • [MR2674623] Go to document 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{MR2674623,
      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},
      url = {https://doi.org/10.1002/rsa.20304},
      zblnumber = {1242.60011},
      }
  • [MR2799807] Go to document E. Lubetzky, B. Sudakov, and V. Vu, "Spectra of lifted Ramanujan graphs," Adv. Math., vol. 227, iss. 4, pp. 1612-1645, 2011.
    @ARTICLE{MR2799807,
      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},
      mrclass = {05C50 (05C75 05C80 68R10)},
      mrnumber = {2799807},
      mrreviewer = {Aleksandar Ilić},
      doi = {10.1016/j.aim.2011.03.016},
      url = {https://doi.org/10.1016/j.aim.2011.03.016},
      zblnumber = {1222.05168},
      }
  • [M13] Go to document L. Massoulié, "Community detection thresholds and the weak Ramanujan property," in STOC’14—Proceedings of the 2014 ACM Symposium on Theory of Computing, 2014, pp. 694-703.
    @INPROCEEDINGS{M13,
      author = {Massoulié,
      Laurent},
      title = {Community detection thresholds and the weak {R}amanujan property},
      booktitle = {S{TOC}'14---{P}roceedings of the 2014 {ACM} {S}ymposium on {T}heory of {C}omputing},
      pages = {694--703},
      publisher = {ACM, New York},
      year = {2014},
      mrclass = {05C85 (05C50)},
      mrnumber = {3238997},
      zblnumber = {1315.68210},
      doi = {10.1145/2591796.2591857},
      url = {https://doi.org/10.1145/2591796.2591857},
      }
  • [MR3585560] Go to document J. A. Mingo and R. Speicher, Free Probability and Random Matrices, Springer, New York; Fields Institute for Research in Mathematical Sciences, Toronto, ON, 2017, vol. 35.
    @BOOK{MR3585560,
      author = {Mingo, James A. and Speicher, Roland},
      title = {Free Probability and Random Matrices},
      series = {Fields Institute Monographs},
      volume = {35},
      publisher = {Springer, New York; Fields Institute for Research in Mathematical Sciences, Toronto, ON},
      year = {2017},
      pages = {xiv+336},
      isbn = {978-1-4939-6941-8; 978-1-4939-6942-5},
      mrclass = {46L54 (05D40 15B52 60B20)},
      mrnumber = {3585560},
      mrreviewer = {Vladislav Kargin},
      doi = {10.1007/978-1-4939-6942-5},
      url = {https://doi.org/10.1007/978-1-4939-6942-5},
      zblnumber = {1387.60005},
      }
  • [MR1074574] Go to document G. J. Murphy, $C^*$-Algebras and Operator Theory, Academic Press, Inc., Boston, MA, 1990.
    @BOOK{MR1074574,
      author = {Murphy, Gerard J.},
      title = {{$C^*$}-Algebras and Operator Theory},
      publisher = {Academic Press, Inc., Boston, MA},
      year = {1990},
      pages = {x+286},
      isbn = {0-12-511360-9},
      mrclass = {46Lxx (46-01)},
      mrnumber = {1074574},
      mrreviewer = {E. Gerlach},
      zblnumber = {0714.46041},
      doi = {10.1016/C2009-0-22289-6},
      url = {https://doi.org/10.1016/C2009-0-22289-6},
      }
  • [MR1197059] Go to document A. Nica, "Asymptotically free families of random unitaries in symmetric groups," Pacific J. Math., vol. 157, iss. 2, pp. 295-310, 1993.
    @ARTICLE{MR1197059,
      author = {Nica, Alexandru},
      title = {Asymptotically free families of random unitaries in symmetric groups},
      journal = {Pacific J. Math.},
      fjournal = {Pacific Journal of Mathematics},
      volume = {157},
      year = {1993},
      number = {2},
      pages = {295--310},
      issn = {0030-8730},
      mrclass = {46L99 (46L50 47B80 60F99)},
      mrnumber = {1197059},
      mrreviewer = {D. Petz},
      doi = {10.2140/pjm.1993.157.295},
      url = {https://doi.org/10.2140/pjm.1993.157.295},
      zblnumber = {0739.46051},
      }
  • [MR2799213] Go to document R. I. Oliveira, "The spectrum of random $k$-lifts of large graphs (with possibly large $k$)," J. Comb., vol. 1, iss. 3-4, pp. 285-306, 2010.
    @ARTICLE{MR2799213,
      author = {Oliveira, Roberto Imbuzeiro},
      title = {The spectrum of random {$k$}-lifts of large graphs (with possibly large {$k$})},
      journal = {J. Comb.},
      fjournal = {Journal of Combinatorics},
      volume = {1},
      year = {2010},
      number = {3-4},
      pages = {285--306},
      issn = {2156-3527},
      mrclass = {05C80 (05C50 05C76 60B20)},
      mrnumber = {2799213},
      mrreviewer = {Stephen J. Young},
      doi = {10.4310/JOC.2010.v1.n3.a2},
      url = {https://doi.org/10.4310/JOC.2010.v1.n3.a2},
      zblnumber = {1244.05147},
      }
  • [MR1401692] Go to document G. Pisier, "A simple proof of a theorem of Kirchberg and related results on $C^*$-norms," J. Operator Theory, vol. 35, iss. 2, pp. 317-335, 1996.
    @ARTICLE{MR1401692,
      author = {Pisier, Gilles},
      title = {A simple proof of a theorem of {K}irchberg and related results on {$C^*$}-norms},
      journal = {J. Operator Theory},
      fjournal = {Journal of Operator Theory},
      volume = {35},
      year = {1996},
      number = {2},
      pages = {317--335},
      issn = {0379-4024},
      mrclass = {46L05 (22D05 22D25 46B28 46M05 47D15)},
      mrnumber = {1401692},
      mrreviewer = {Wend Werner},
      zblnumber = {0858.46045},
      url = {http://www.mathjournals.org/jot/1996-035-002/1996-035-002-005.pdf},
      }
  • [MR3226740] Go to document G. Pisier, "Quantum expanders and geometry of operator spaces," J. Eur. Math. Soc. (JEMS), vol. 16, iss. 6, pp. 1183-1219, 2014.
    @ARTICLE{MR3226740,
      author = {Pisier, Gilles},
      title = {Quantum expanders and geometry of operator spaces},
      journal = {J. Eur. Math. Soc. (JEMS)},
      fjournal = {Journal of the European Mathematical Society (JEMS)},
      volume = {16},
      year = {2014},
      number = {6},
      pages = {1183--1219},
      issn = {1435-9855},
      mrclass = {46L07 (05C90 47A10)},
      mrnumber = {3226740},
      mrreviewer = {Stefan Waldmann},
      doi = {10.4171/JEMS/458},
      url = {https://doi.org/10.4171/JEMS/458},
      zblnumber = {1307.46045},
      }
  • [MR3385636] Go to document D. Puder, "Expansion of random graphs: new proofs, new results," Invent. Math., vol. 201, iss. 3, pp. 845-908, 2015.
    @ARTICLE{MR3385636,
      author = {Puder, Doron},
      title = {Expansion of random graphs: new proofs, new results},
      journal = {Invent. Math.},
      fjournal = {Inventiones Mathematicae},
      volume = {201},
      year = {2015},
      number = {3},
      pages = {845--908},
      issn = {0020-9910},
      mrclass = {05C80 (05E18)},
      mrnumber = {3385636},
      mrreviewer = {Kunal Dutta},
      doi = {10.1007/s00222-014-0560-x},
      url = {https://doi.org/10.1007/s00222-014-0560-x},
      zblnumber = {1320.05115},
      }
  • [NIPS2009_0420] Go to document Y. Watanabe and K. Fukumizu, "Graph zeta Function in the Bethe Free Energy and Loopy Belief Propagation," in Advances in Neural Information Processing Systems 22, , 2009, pp. 2017-2025.
    @INCOLLECTION{NIPS2009_0420,
      author = {Watanabe, Y. and Fukumizu, K.},
      title = {Graph zeta Function in the {B}ethe Free Energy and {L}oopy {B}elief {P}ropagation},
      booktitle = {Advances in Neural Information Processing Systems 22},
      pages = {2017--2025},
      year = {2009},
      note = {(Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta, editors)},
      zblnumber = {},
      url = {https://papers.nips.cc/paper/3779-graph-zeta-function-in-the-bethe-free-energy-and-loopy-belief-propagation},
      }

Authors

Charles Bordenave

Institut Mathématiques de Marseille, Marseille, France

Benoît Collins

Department of Mathematics, Kyoto University, Kyoto, Japan