We study the spectrum of a random multigraph with a degree sequence ${bf D}_n=(D_i)_{i=1}^n$ and average degree $1 ll omega_n ll n$, generated by the configuration model, and also the spectrum of the analogous random simple graph. We show that, when the empirical spectral distribution (ESD) of $omega_n^{-1} {bf D}_n $ converges weakly to a limit $ u$, under mild moment assumptions (e.g., $D_i/omega_n$ are i.i.d. with a finite second moment), the ESD of the normalized adjacency matrix converges in probability to $ uboxtimes sigma_{rm sc}$, the free multiplicative convolution of $ u$ with the semicircle law. Relating this limit with a variant of the Marchenko--Pastur law yields the continuity of its density (away from zero), and an effective procedure for determining its support. Our proof of convergence is based on a coupling between the random simple graph and multigraph with the same degrees, which might be of independent interest. We further construct and rely on a coupling of the multigraph to an inhomogeneous ErdH{o}s-Renyi graph with the target ESD, using three intermediate random graphs, with a negligible fraction of edges modified in each step.
تحميل البحث