Eigenvalues of random lifts and polynomials of random permutation matrices

Abstract

Consider 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 goes to infinity, these permutations viewed as operators on the (n-1) dimensional vector space orthogonal to the vector with all coordinates equal to 1, 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.

typos corrected and clarified proof of Theorem 2

Cited by in corpus (9)

• A random cover of a compact hyperbolic surface has relative spectral gap $\frac{3}{16}-\epsilon$
• Word Measures on Symmetric Groups
• Cutoff at the entropic time for random walks on covered expander graphs
• Aldous' Spectral Gap Conjecture for Normal Sets
• Strong asymptotic freeness for independent uniform variables on compact groups associated to non-trivial representations
• A Note on the Trace Method for Random Regular Graphs
• A note on quantum expanders
• Universality of free random variables: atoms for non-commutative rational functions
• ${\mathrm{SL}}_4(\mathbf{Z})$ is not purely matricial field