×

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)].

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI