The first eigenvalue of random graphs. (English) Zbl 1077.05092
Z. Füredi and J. Komlós [Combinatorica 1, 233–241 (1981; Zbl 0494.15010)] showed that for constant \(p\in(0,1)\), the first eigenvalue \(\lambda_1\) of the adjacency matrix of the random graph \(G_{n,p}\) is asymptotically normal. Here, the author first extends this result to \(p\mapsto 0\) provided \(np\gg n^\delta\) for some \(\delta>0\). Next, if \(m/\binom{n}{2}\mapsto p\in[0,1)\) and \(m\gg n^{1+\delta}\) for some \(\delta>0\), then it is shown that \(\lambda_1(G_{n,m})\) is also asymptotically normal with an asymptotic variance of order \(n^{-1}\).
These two results give partial answer to a question of M. Krivelevich and B. Sudakov [Comb. Probab. Comput. 12, 61–72 (2003; Zbl 1012.05109)].
These two results give partial answer to a question of M. Krivelevich and B. Sudakov [Comb. Probab. Comput. 12, 61–72 (2003; Zbl 1012.05109)].
Reviewer: Dragan Stevanović (Niš)
MSC:
05C80 | Random graphs (graph-theoretic aspects) |
05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |