Spectrum of Markov generators on sparse random graphs

Abstract

We investigate the spectrum of the infinitesimal generator of the continuous time random walk on a randomly weighted oriented graph. This is the non-Hermitian random nxn matrix L defined by L(j,k)=X(j,k) if k<>j and L(j,j)=-sum(L(j,k),k<>j), where X(j,k) are i.i.d. random weights. Under mild assumptions on the law of the weights, we establish convergence as n tends to infinity of the empirical spectral distribution of L after centering and rescaling. In particular, our assumptions include sparse random graphs such as the oriented Erdös-Rényi graph where each edge is present independently with probability p(n)->0 as long as np(n) >> (log(n))^6. The limiting distribution is characterized as an additive Gaussian deformation of the standard circular law. In free probability terms, this coincides with the Brown measure of the free sum of the circular element and a normal operator with Gaussian spectral measure. The density of the limiting distribution is analyzed using a subordination formula. Furthermore, we study the convergence of the invariant measure of L to the uniform distribution and establish estimates on the extremal eigenvalues of L.

Correction in Proposition 4.3. Final version

Cited by in corpus (12)

• Random Lindblad Dynamics
• Circular law for random matrices with exchangeable entries
• Random generators of Markovian evolution: A quantum-classical transition by superdecoherence
• Spectra of Random Stochastic Matrices and Relaxation in Complex Systems
• Circular law for random matrices with unconditional log-concave distribution
• Random matrices with row constraints and eigenvalue distributions of graph Laplacians
• Disentangling Giant Component and Finite Cluster Contributions in Sparse Matrix Spectra
• From Boltzmann to random matrices and beyond
• Quaternionic R transform and non-hermitian random matrices
• Random sparse generators of Markovian evolution and their spectral properties
• Random Lindblad operators obeying detailed balance
• Limiting eigenvalue distribution of the general deformed Ginibre ensemble