×

zbMATH — the first resource for mathematics

Eigenvalues of random lifts and polynomials of random permutation matrices. (English) Zbl 1446.60004
The authors prove, along with a number of other results, the following: suppose that \((\sigma_1,\dots,\sigma_d)\) is a finite sequence of independent random permutations, chosen uniformly among all permutations or among all matchings on \(N\) points. Then it is shown that, in probability, as \(N\to \infty\), these permutations viewed as operators on the \((N-1)\)-dimensional vector space \(\left\{(x_1,\dots,x_N)\in \mathbb{C}^N:\sum_{i=1}^Nx_i=0 \right\}\) are asymptotically strongly free. Moreover, as a byproduct, the authors obtain that the non-trivial eigenvalues of random \(N\)-lifts of a fixed base graph achieve, up to a vanishing term, the so-called Alon-Boppana lower bound with high probability as \(N\to \infty\). This settles a conjecture of J. Friedman [Duke Math. J. 118, No. 1, 19–35 (2003; Zbl 1035.05058)].
The main contribution of this paper can in fact be understood as a novel use of non-backtracking operators, since the authors reduce the results above to establishing analogous ones for non-backtracking operators. Then, the strategy of proof of these results on non-backtracking operators is similar to the one followed by the first author to give a new proof of Friedman’s theorem in [“A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts”, Preprint, arXiv:1502.04482], but with a number of significant refinements which require a very delicate analysis.
Finally, extensions of the results mentioned above to tensor products of random permutation matrices are also discussed.

MSC:
60B20 Random matrices (probabilistic aspects)
05C80 Random graphs (graph-theoretic aspects)
46L54 Free probability and free operator algebras
Citations:
Zbl 1035.05058
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Addario-Berry, L.; Griffiths, S., The spectrum of random lifts (2010)
[2] Akemann, Charles A.; Ostrand, Phillip A., Computing norms in group {\(C\sp*\)}-algebras, Amer. J. Math.. American Journal of Mathematics, 98, 1015-1047 (1976) · Zbl 0342.22008
[3] Aldous, David; Lyons, Russell, Processes on unimodular random networks, Electron. J. Probab.. Electronic Journal of Probability, 12, 54-1454 (2007) · Zbl 1131.60003
[4] Amit, Alon; Linial, Nathan, Random graph coverings. {I}. {G}eneral theory and graph connectivity, Combinatorica. Combinatorica. An International Journal on Combinatorics and the Theory of Computing, 22, 1-18 (2002) · Zbl 0996.05105
[5] Amit, Alon; Linial, Nathan, Random lifts of graphs: edge expansion, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 15, 317-332 (2006) · Zbl 1095.05034
[6] Anantharaman, Nalini, Quantum ergodicity on regular graphs, Comm. Math. Phys.. Communications in Mathematical Physics, 353, 633-690 (2017) · Zbl 1368.58015
[7] Anderson, Greg W., Convergence of the largest singular value of a polynomial in independent {W}igner matrices, Ann. Probab.. The Annals of Probability, 41, 2103-2181 (2013) · Zbl 1282.60007
[8] Bordenave, Charles, Spectrum of random graphs. Advanced {T}opics in {R}andom {M}atrices, Panor. Synth\`eses, 53, 91-150 (2017) · Zbl 1395.05149
[9] Bordenave, Charles, A new proof of {F}riedman{’}s second eigenvalue theorem and its extension to random lifts (2122)
[10] Bordenave, Charles; Lelarge, Marc; Massouli\'{e}, Laurent, Nonbacktracking spectrum of random graphs: community detection and nonregular {R}amanujan graphs, Ann. Probab.. The Annals of Probability, 46, 1-71 (2018) · Zbl 1386.05174
[11] Buchholz, Artur, Norm of convolution by operator-valued functions on free groups, Proc. Amer. Math. Soc.. Proceedings of the American Mathematical Society, 127, 1671-1682 (1999) · Zbl 0916.43002
[12] Ceccherini-Silberstein, Tullio; Scarabotti, Fabio; Tolli, Filippo, Weighted expanders and the anisotropic {A}lon-{B}oppana theorem, European J. Combin.. European Journal of Combinatorics, 25, 735-744 (2004) · Zbl 1048.05057
[13] Collins, Benoit; Gaudreau Lamarre, Pierre Yves, {\( \ast \)}-freeness in finite tensor products, Adv. in Appl. Math.. Advances in Applied Mathematics, 83, 47-80 (2017) · Zbl 1369.46059
[14] Collins, Beno\^{\i}t; Male, Camille, The strong asymptotic freeness of {H}aar and deterministic matrices, Ann. Sci. \'{E}c. Norm. Sup\'{e}r. (4). Annales Scientifiques de l’\'{E}cole Normale Sup\'{e}rieure. Quatri\`“eme S\'”{e}rie, 47, 147-163 (2014) · Zbl 1303.15043
[15] Deimling, Klaus, Nonlinear {F}unctional {A}nalysis, xiv+450 pp. (1985) · Zbl 1257.47059
[16] Fig\`{a}-Talamanca, Alessandro; Steger, Tim, Harmonic analysis for anisotropic random walks on homogeneous trees, Mem. Amer. Math. Soc.. Memoirs of the American Mathematical Society, 110, xii+68 pp. (1994) · Zbl 0836.43019
[17] Friedman, Joel, Relative expanders or weakly relatively {R}amanujan graphs, Duke Math. J.. Duke Mathematical Journal, 118, 19-35 (2003) · Zbl 1035.05058
[18] Friedman, Joel, A proof of {A}lon’s second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc.. Memoirs of the American Mathematical Society, 195, viii+100 pp. (2008) · Zbl 1177.05070
[19] Friedman, Joel; Joux, A.; Roichman, Y.; Stern, J.; Tillich, J. P., The action of a few random permutations on \(r\)-tuples and an application to cryptography. S{TACS} 96, Lecture Notes in Comput. Sci., 1046, 375-386 (1996) · Zbl 1380.94089
[20] Friedman, Joel; Kohler, D.-E., The relativized second eigenvalue conjecture of alon (2014)
[21] F\`“{u}redi, Z.; Koml\'”{o}s, J., The eigenvalues of random symmetric matrices, Combinatorica. Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society, 1, 233-241 (1981) · Zbl 0494.15010
[22] Greenberg, Y., Spectra of graphs and their covering trees (1995)
[23] Gross, Leonard, Existence and uniqueness of physical ground states, J. Functional Analysis, 10, 52-109 (1972) · Zbl 0237.47012
[24] Haagerup, Uffe; Thorbj{\o}rnsen, Steen, A new application of random matrices: {\({\rm Ext}(C^*_{\rm red}(F_2))\)} is not a group, Ann. of Math. (2). Annals of Mathematics. Second Series, 162, 711-775 (2005) · Zbl 1103.46032
[25] Hastings, M. B., Random unitaries give quantum expanders, Phys. Rev. A (3). Physical Review. A. Third Series, 76, 032315-11 (2007)
[26] Hastings, M. B.; Harrow, A. W., Classical and quantum tensor product expanders, Quantum Inf. Comput.. Quantum Information & Computation, 9, 336-360 (2009) · Zbl 1171.81329
[27] Kre\u{\i}n, M. G.; Rutman, M. A., Linear operators leaving invariant a cone in a {B}anach space, Amer. Math. Soc. Translation. American Mathematical Society Translations, 1950, 128 pp. (1950)
[28] Lehner, Franz, Computing norms of free operators with matrix coefficients, Amer. J. Math.. American Journal of Mathematics, 121, 453-486 (1999) · Zbl 0929.22004
[29] Linial, Nati; Puder, Doron, Word maps and spectra of random graph lifts, Random Structures Algorithms. Random Structures & Algorithms, 37, 100-135 (2010) · Zbl 1242.60011
[30] Lubetzky, Eyal; Sudakov, Benny; Vu, Van, Spectra of lifted {R}amanujan graphs, Adv. Math.. Advances in Mathematics, 227, 1612-1645 (2011) · Zbl 1222.05168
[31] Massouli\'{e}, Laurent, Community detection thresholds and the weak {R}amanujan property. S{TOC}’14—{P}roceedings of the 2014 {ACM} {S}ymposium on {T}heory of {C}omputing, 694-703 (2014) · Zbl 1315.68210
[32] Mingo, James A.; Speicher, Roland, Free Probability and Random Matrices, Fields Institute Monographs, 35, xiv+336 pp. (2017) · Zbl 1387.60005
[33] Murphy, Gerard J., {\(C^*\)}-Algebras and Operator Theory, x+286 pp. (1990) · Zbl 0714.46041
[34] Nica, Alexandru, Asymptotically free families of random unitaries in symmetric groups, Pacific J. Math.. Pacific Journal of Mathematics, 157, 295-310 (1993) · Zbl 0739.46051
[35] Oliveira, Roberto Imbuzeiro, The spectrum of random {\(k\)}-lifts of large graphs (with possibly large {\(k\)}), J. Comb.. Journal of Combinatorics, 1, 285-306 (2010) · Zbl 1244.05147
[36] Pisier, Gilles, A simple proof of a theorem of {K}irchberg and related results on {\(C^*\)}-norms, J. Operator Theory. Journal of Operator Theory. http://www.mathjournals.org/jot/1996-035-002/1996-035-002-005.pdf, 35, 317-335 (1996) · Zbl 0858.46045
[37] Pisier, Gilles, Quantum expanders and geometry of operator spaces, J. Eur. Math. Soc. (JEMS). Journal of the European Mathematical Society (JEMS), 16, 1183-1219 (2014) · Zbl 1307.46045
[38] Puder, Doron, Expansion of random graphs: new proofs, new results, Invent. Math.. Inventiones Mathematicae, 201, 845-908 (2015) · Zbl 1320.05115
[39] Watanabe, Y.; Fukumizu, K., Graph zeta Function in the {B}ethe Free Energy and {L}oopy {B}elief {P}ropagation. Advances in Neural Information Processing Systems 22, 2017-2025 (2009)
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.