Consider a finite sequence of independent random permutations, chosenuniformly either among all permutations or among all matchings on n points. Weshow that, in probability, as n goes to infinity, these permutations viewed asoperators on the (n-1) dimensional vector space orthogonal to the vector withall coordinates equal to 1, are asymptotically strongly free. Our proof relieson the development of a matrix version of the non-backtracking operator theoryand a refined trace method. As a byproduct, we show that the non-trivial eigenvalues of random n-lifts ofa fixed based graphs approximately achieve the Alon-Boppana bound with highprobability in the large n limit. This result generalizes Friedman's Theoremstating that with high probability, the Schreier graph generated by a finitenumber of independent random permutations is close to Ramanujan. Finally, we extend our results to tensor products of random permutationmatrices. This extension is especially relevant in the context of quantumexpanders.
展开▼
