Spectra of edge-independent random graphs

Abstract

Let $G$ be a random graph on the vertex set $\{1,2,...,n\}$ such that edges in $G$ are determined by independent random indicator variables, while the probability $p_{ij}$ for $\{i,j\}$ being an edge in $G$ is 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=\E(A)$, and $\Delta$ be the maximum expected degree of $G$. Oliveira first proved that almost surely $\Vert A-\bar{A}\Vert =O(\sqrt{\Delta \ln n})$ provided $\Delta \ge 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 almost surely $\Vert A-\bar{A}\Vert \le (2+o(1))\sqrt{\Delta }$ with a slightly stronger condition $\Delta \gg {\ln }^{4}n$. For the Laplacian $L$ of $G$, Oliveira and Chung-Radcliffe proved similar results $\Vert L-\bar{L}|=O(\sqrt{\ln n}/\sqrt{\delta })$ provided the minimum expected degree $\delta \gg \ln n$; 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 classic Erdős-Rényi random graphs, random graphs with given expected degree sequences, and bond percolation of general graphs.

16 pages

Cited by in corpus (1)

• Testing goodness-of-fit of random graph models