Spectra of large diluted but bushy random graphs (Q2818279)

Let \(G(n.c/n)\) be an Erdős-Rényi random graph and \(\mu^{c}\) be the limit of the empirical spectral measures of the adjacency matrices of these graphs as \(n\rightarrow\infty\). (The empirical spectral measure assigns to a set \(S\subseteq \mathbb{R}\) the number of eigenvalues of the adjacency matrix which are in \(S\), divided by \(n\).) It is well known that \(\mu^{c}\) exists and depends on \(c\) (unlike the situation for \(G(n,p)\) where \(\lim_{n\rightarrow\infty}np=\infty\), when the limit of the empirical spectral measures is always the Wigner semi-circle law).NEWLINENEWLINEThe aim of the paper under review is to understand \(\mu^{c}\) better for large \(c\). In detail, what is done is to work out an asymptotic expansion of \(\mu^{c}\) in terms of \(1/c\). The proofs depend on computing moments of \(\mu^{c}\), which turn out to be closely related to closed walks on the graphs -- it turns out that only certain walks contribute. While the main term in the expansion is again Wigner's semi-circle law, the derivation of the second order term involves delicate computations with generating functions, and moving around between the sparse graphs and the infinite tree which they approximate as \(n\rightarrow\infty\).