
arXiv: 1204.6207
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.
Eigenvalues, singular values, and eigenvectors, Graphs and linear algebra (matrices, eigenvalues, etc.), Random graphs (graph-theoretic aspects), eigenvalues, random matrix, Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.), edge-independent random graph, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Laplacian, 05C80, 05D40, 15A18
Eigenvalues, singular values, and eigenvectors, Graphs and linear algebra (matrices, eigenvalues, etc.), Random graphs (graph-theoretic aspects), eigenvalues, random matrix, Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.), edge-independent random graph, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Laplacian, 05C80, 05D40, 15A18
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 22 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
