Spectrum of Markov generators on sparse random graphs
Chafaï, Djalil; Caputo, Pietro; Bordenave, Charles (2014), Spectrum of Markov generators on sparse random graphs, Communications on Pure and Applied Mathematics, 67, 4, p. 621669. http://dx.doi.org/10.1002/cpa.21496
View/Open
Type
Article accepté pour publication ou publiéDate
2014Journal name
Communications on Pure and Applied MathematicsVolume
67Number
4Publisher
WileyBlackwell
Pages
621669
Publication identifier
Metadata
Show full item recordAbstract (EN)
We investigate the spectrum of the infinitesimal generator of the continuous time random walk on a randomly weighted oriented graph. This is the nonHermitian 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ősRé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.Subjects / Keywords
Spectral Analysis; Combinatorics; Free probability; Random matrices; Random graphsRelated items
Showing items related by title and author.

Bordenave, Charles; Caputo, Pietro; Chafaï, Djalil; Piras, Daniele (2017) Article accepté pour publication ou publié

Bordenave, Charles; Caputo, Pietro; Chafaï, Djalil; Tikhomirov, Konstantin (2018) Article accepté pour publication ou publié

Bordenave, Charles; Chafaï, Djalil; GarcíaZelada, David (2021) Article accepté pour publication ou publié

Coste, Simon; Salez, Justin (2021) Article accepté pour publication ou publié

Caputo, Pietro; Labbé, Cyril; Lacoin, Hubert (2020) Document de travail / Working paper