Eigenvalues of random lifts and polynomials of random permutation matrices
The authors prove, along with a number of other results, the following: suppose that \((\sigma_1,\dots,\sigma_d)\) is a finite sequence of independent random permutations, chosen uniformly among all permutations or among all matchings on \(N\) points. Then it is shown that, in probability, as \(N\to \infty\), these permutations viewed as operators on the \((N-1)\)-dimensional vector space \(\left\{(x_1,\dots,x_N)\in \mathbb{C}^N:\sum_{i=1}^Nx_i=0 \right\}\) are asymptotically strongly free. Moreover, as a byproduct, the authors obtain that the non-trivial eigenvalues of random \(N\)-lifts of a fixed base graph achieve, up to a vanishing term, the so-called Alon-Boppana lower bound with high probability as \(N\to \infty\). This settles a conjecture of \textit{J. Friedman} [Duke Math. J. 118, No. 1, 19--35 (2003; Zbl 1035.05058)]. The main contribution of this paper can in fact be understood as a novel use of non-backtracking operators, since the authors reduce the results above to establishing analogous ones for non-backtracking operators. Then, the strategy of proof of these results on non-backtracking operators is similar to the one followed by the first author to give a new proof of Friedman's theorem in [``A new proof of Friedman's second eigenvalue theorem and its extension to random lifts, Preprint, \url{arXiv:1502.04482}], but with a number of significant refinements which require a very delicate analysis. Finally, extensions of the results mentioned above to tensor products of random permutation matrices are also discussed.
- \({\ast}\)-freeness in finite tensor products
- 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
- 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?)
- 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 graph coverings. I: General theory and graph connectivity
- Random Lifts of Graphs: Edge Expansion
- 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
- The spectral norm of random lifts of matrices
- Cutoff for random lifts of weighted graphs
- On a linearization trick
- On fluctuations of eigenvalues of random permutation matrices
- A random cover of a compact hyperbolic surface has relative spectral gap \(\frac{3}{16}-\varepsilon\)
- On smooth mesoscopic linear statistics of the eigenvalues of random permutation matrices
- Sparse matrices: convergence of the characteristic polynomial seen from infinity
- Word maps and spectra of random graph lifts
- scientific article; zbMATH DE number 1242982 (Why is no real title available?)
- Weak containment of measure-preserving group actions
- A random matrix approach to the Peterson-Thom conjecture
- Cutoff at the entropic time for random walks on covered expander graphs
- Aldous's spectral gap conjecture for normal sets
- The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
- A note on the trace method for random regular graphs
- Spectra of infinite graphs via freeness with amalgamation
- Near optimal spectral gaps for hyperbolic surfaces
- An exotic \(\mathrm{II}_1\) factor without property Gamma
- Moment methods on compact groups: Weingarten calculus and its applications
- 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]
- Spectrum of random d‐regular graphs up to the edge
- Strong asymptotic freeness for independent uniform variables on compact groups associated to nontrivial representations
- \(\mathrm{SL}_4(\mathbf{Z})\) is not purely matricial field
- Universality and sharp matrix concentration inequalities
- Sparse random hypergraphs: non-backtracking spectra and community detection
- Strongly convergent unitary representations of limit groups
- A note on quantum expanders
- Spectral convergence of random regular graphs: Chebyshev polynomials, non-backtracking walks, and unitary-color extensions
- Non-Hermitian expander obtained with Haar distributed unitaries
- Random permutation matrix models for graph products
- Spectral gap of a convex combination of a random permutation and a deterministic matrix
- Weingarten calculus for centered random permutation matrices
- Strong convergence for tensor GUE random matrices
- Strongly convergent unitary representations of right-angled Artin groups
- A new approach to strong convergence
- Eigenvalues of universal covers and the matching polynomial
- A new approach to strong convergence. II: The classical ensembles
- Limit points of uniform arithmetic bass notes
- Spectral statistics of the Laplacian on random covers of a closed negatively curved surface
- Explicit spectral gaps for random covers of Riemann surfaces
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)
