Spectra of Edge-Independent Random Graphs

Source abstract

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 Oliveira and Chung-Radcliffe. Let $A$ be the adjacency matrix of $G$, $\bar A={\rm E}(A)$, and $\Delta$ be the maximum expected degree of $G$. Oliveira 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 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 and Chung-Radcliffe 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.