Sparse random matrices: Spectral edge and statistics of rooted trees

Following Furedi and Komlos, we develop a graph theory method to study the high moments of large random matrices with independent entries. We apply this method to sparse N x N random matrices A(N. p) that have, on average, p non-zero elements per row. One of our results is related to the asymptotic behaviour of the spectral norm parallel toA(N,p)parallel to in the limit 1 much less than p much less than N. We show that the value p(c) = log N is the critical one for lim parallel to A(N,p) /rootp parallel to to be bounded or not. We discuss relations of this result with the Erdos-Renyi limit theorem and properties of large random graphs. In the proof, the principal issue is that the averaged vertex degree of plane rooted trees of k edges remains bounded even when k --> infinity. This observation implies fairly precise estimates for the moments of A(N.p) They lead to certain generalizations of the results by Sinai and Soshnikov on the universality of local spectral statistics at the border of the limiting spectra of large random matrices.