Concentration of the spectral norm of Erdős-Rényi random graphs (Q2175000)

This paper studies some inequalities for the uniform concentration of the largest adjacency eigenvalue \(\lambda_p\) for E-R random graph \(G(n,p)\). The largest adjacency eigenvalue is equivalent to the spectral norm of the adjacency matrix \(\|A_p\|\), where \(A_p\) is the adjacency matrix of the random graph \(G(n,p)\). It is shown that there is \(C>0\) such that \(\mathbb{E}\sup|\lambda_p-\mathbb{E}\lambda_p|\le C\), where the supremum is taken over \(p\in[64(\ln n)/n,1]\). Moreover, for any \(t\ge 2C\), \(\mathbb{P}(\sup|\lambda_p-\mathbb{E}\lambda_p|\ge t)\le\exp(-t^2/128)\), where the supremum is taken on the same interval.