Spectra of edge-independent random graphs (Q396954)

Summary: Let \(G\) be a random graph on the vertex set \(\{1,2,\ldots, n\}\) such that edges in \(G\) are determined by independent random indicator variables, while the probabilities \(p_{ij}\) for \(\{i,j\}\) being an edge in \(G\) are not assumed to be equal. Spectra of the adjacency matrix and the normalized Laplacian matrix of \(G\) are recently studied by \textit{R. Oliveira} [``Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges'', Preprint, \url{arXiv:0911.0600}] and \textit{F. Chung} and \textit{M. Radcliffe} [Electron. J. Comb. 18, No. 1, Research Paper P215, 14 p. (2011; Zbl 1229.05248)]. Let \(A\) be the adjacency matrix of \(G, \bar A=\text{ E}(A)\), and \(\Delta\) be the maximum expected degree of \(G\). Oliveira [loc. cit.] first proved that asymptotically almost surely \(\|A-\bar A\|=O(\sqrt{\Delta \ln n})\) provided \(\Delta\geq C \ln n\) for some constant \(C\). Chung-Radcliffe [loc. cit.] improved the hidden constant in the error term using a new Chernoff-type inequality for random matrices. Here we prove that asymptotically almost surely \(\|A-\bar A\|\leq (2+o(1))\sqrt{\Delta}\) with a slightly stronger condition \(\Delta\gg \ln^4 n\). For the Laplacian matrix \(L\) of \(G\), Oliveira [loc. cit.] and Chung-Radcliffe [loc. cit.] proved similar results \(\|L-\bar L\|=O(\sqrt{\ln n}/\sqrt{\delta})\) provided the minimum expected degree \(\delta\geq C' \ln n\) for some constant \(C'\); we also improve their results by removing the \(\sqrt{\ln n}\) multiplicative factor from the error term under some mild conditions. Our results naturally apply to the classical Erdős-Rényi random graphs, random graphs with given expected degree sequences, and bond percolation of general graphs.