Eigenvalues of random lifts and polynomials of random permutation matrices
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 48576 (Why is no real title available?)
- scientific article; zbMATH DE number 6902684 (Why is no real title available?)
- scientific article; zbMATH DE number 936703 (Why is no real title available?)
- scientific article; zbMATH DE number 6132668 (Why is no real title available?)
- A new application of random matrices: \(\operatorname{Ext} (C_{\text{red}}^*(F_2))\) is not a group
- A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
- A proof of Alon’s second eigenvalue conjecture and related problems
- Asymptotically free families of random unitaries in symmetric groups
- Classical and quantum tensor product expanders
- Community detection thresholds and the weak Ramanujan property
- Computing Norms in Group C ∗ -Algebras
- Computing norms of free operators with matrix coefficients
- Convergence of the largest singular value of a polynomial in independent Wigner matrices
- Existence and uniqueness of physical ground states
- Expansion of random graphs: new proofs, new results
- Harmonic analysis for anisotropic random walks on homogeneous trees
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- Norm of convolution by operator-valued functions on free groups
- Processes on unimodular random networks
- Quantum ergodicity on regular graphs
- Quantum expanders and geometry of operator spaces
- Random Lifts of Graphs: Edge Expansion
- Random graph coverings. I: General theory and graph connectivity
- Relative expanders or weakly relatively Ramanujan graphs.
- Spectra of lifted Ramanujan graphs
- The action of a few random permutations on r-tuples and an application to cryptography
- The eigenvalues of random symmetric matrices
- The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
- The strong asymptotic freeness of Haar and deterministic matrices
- Weighted expanders and the anisotropic Alon-Boppana theorem
- Word maps and spectra of random graph lifts
- \({\ast}\)-freeness in finite tensor products
Cited in
(28)- Weak containment of measure-preserving group actions
- Explicit spectral gaps for random covers of Riemann surfaces
- Universality of free random variables: atoms for non-commutative rational functions
- Exposé Bourbaki 1202 : Strong convergence of the spectrum of random permutations and almost-Ramanujan graphs [after Charles Bordenave and Benoît Collins]
- scientific article; zbMATH DE number 1242982 (Why is no real title available?)
- A random cover of a compact hyperbolic surface has relative spectral gap \(\frac{3}{16}-\varepsilon\)
- On a linearization trick
- A random matrix approach to the Peterson-Thom conjecture
- Strong asymptotic freeness for independent uniform variables on compact groups associated to nontrivial representations
- The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
- Spectrum of random d‐regular graphs up to the edge
- Cutoff at the entropic time for random walks on covered expander graphs
- Cutoff for random lifts of weighted graphs
- Aldous's spectral gap conjecture for normal sets
- Near optimal spectral gaps for hyperbolic surfaces
- On smooth mesoscopic linear statistics of the eigenvalues of random permutation matrices
- Word maps and spectra of random graph lifts
- A note on the trace method for random regular graphs
- On fluctuations of eigenvalues of random permutation matrices
- \(\mathrm{SL}_4(\mathbf{Z})\) is not purely matricial field
- An exotic \(\mathrm{II}_1\) factor without property Gamma
- The spectral norm of random lifts of matrices
- Universality and sharp matrix concentration inequalities
- Sparse matrices: convergence of the characteristic polynomial seen from infinity
- Strongly convergent unitary representations of limit groups
- Spectra of infinite graphs via freeness with amalgamation
- Sparse random hypergraphs: non-backtracking spectra and community detection
- Moment methods on compact groups: Weingarten calculus and its applications
This page was built for publication: Eigenvalues of random lifts and polynomials of random permutation matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2334866)
