Eigenvalues of random lifts and polynomials of random permutation matrices
By Charles Bordenave, Benoît Collins. Annals of Mathematics, 2018
116 citations recorded by the source corpus.
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.
Subfields: Discrete Mathematics and Combinatorics, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/ad73f598dabb185ed2b05819d0721de1056c51a9
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Discrete Mathematics and Combinatorics
In Statistics and Probability
Citations in the corpus
- Tensor Products of C*-Algebras and Operator Spaces (2020, background): “Bordenave and Collins [32] also prove a result that yields quantum expanders derived from permutation matrices.”
- A random matrix approach to the Peterson-Thom conjecture (2020, methodology): “have been used in combination with delicate analytic and combinatorial arguments to establish strong convergence for many other ensembles, and also for a mixture of random and deterministic ensembles [49, 16, 4]. In particular, recent work [58, 15] shows that if mk is a sequence of positive integers”