Eigenvalues of random lifts and polynomials of random permutation matrices

DOI10.4007/annals.2019.190.3.3zbMath1446.60004arXiv1801.00876OpenAlexW3103237002MaRDI QIDQ2334866

Charles Bordenave, Benoit Collins

Publication date: 8 November 2019

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1801.00876

zbMATH Keywords

random permutationrandom liftsnon-backtracking operatorstrong asymptotic freeness

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Free probability and free operator algebras (46L54)

Related Items (17)

Cutoff for random lifts of weighted graphs ⋮ Explicit spectral gaps for random covers of Riemann surfaces ⋮ A random matrix approach to the Peterson-Thom conjecture ⋮ A random cover of a compact hyperbolic surface has relative spectral gap \(\frac{3}{16}-\varepsilon\) ⋮ CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS ⋮ 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 ⋮ Sparse matrices: convergence of the characteristic polynomial seen from infinity ⋮ Spectrum of random d‐regular graphs up to the edge ⋮ Aldous’s spectral gap conjecture for normal sets ⋮ Weak containment of measure-preserving group actions ⋮ The spectral norm of random lifts of matrices ⋮ On a linearization trick

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \({\ast}\)-freeness in finite tensor products
• Convergence of the largest singular value of a polynomial in independent Wigner matrices
• Expansion of random graphs: new proofs, new results
• Free probability and random matrices
• The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
• Spectra of lifted Ramanujan graphs
• Random graph coverings. I: General theory and graph connectivity
• Asymptotically free families of random unitaries in symmetric groups
• The eigenvalues of random symmetric matrices
• Relative expanders or weakly relatively Ramanujan graphs.
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Weighted expanders and the anisotropic Alon-Boppana theorem
• Quantum ergodicity on regular graphs
• Processes on unimodular random networks
• A new application of random matrices: \(\operatorname{Ext} (C_{\text{red}}^*(F_2))\) is not a group
• Quantum expanders and geometry of operator spaces
• Existence and uniqueness of physical ground states
• Word maps and spectra of random graph lifts
• 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
• Computing Norms in Group C ∗ -Algebras
• Norm of convolution by operator-valued functions on free groups
• Computing norms of free operators with matrix coefficients
• Harmonic analysis for anisotropic random walks on homogeneous trees
• The action of a few random permutations on r-tuples and an application to cryptography
• Community detection thresholds and the weak Ramanujan property
• Random Lifts of Graphs: Edge Expansion
• The strong asymptotic freeness of Haar and deterministic matrices

This page was built for publication: Eigenvalues of random lifts and polynomials of random permutation matrices