The Largest Eigenvalue of Sparse Random Graphs
The Largest Eigenvalue of Sparse Random Graphs
We prove that, for all values of the edge probability $p(n)$, the largest eigenvalue of the random graph $G(n, p)$ satisfies almost surely $\lambda_1(G)=(1+o(1))\max\{\sqrt{\Delta}, np\}$, where Δ is the maximum degree of $G$, and the o(1) term tends to zero as $\max\{\sqrt{\Delta}, np\}$ tends to infinity.