Eigenvalues of random lifts and polynomials of random permutation matrices

• 成果类型: Article
• 署名作者: Bordenave, Charles; Collins, Benoit
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2019.190.3.3
• 发表日期: 2019
• 页码: 811-875
• 关键词: computing norms; graphs; expanders; freeness; SPECTRA

摘要

Let (sigma(1), . . . , 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 -> infinity, these permutations viewed as operators on the n-1 dimensional vector space {x(1), . . . , x(n)) is an element of C-n, Sigma 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.