Random incidence matrices: Moments of the spectral density

We study numerically and analytically the spectrum of incidence matrices of random labeled graphs on N vertices: any pair of vertices is connected by an edge with probability p. We give two algorithms to compute the moments o f the eigenvalue distribution as explicit polynomials in iv and p. For larg e N and fixed p, the spectrum contains a large eigenvalue at Np and a semic ircle of "small" eigenvalues. For large N and fixed average connectivity pN (dilute or sparse random mall ices limit) we show that the spectrum always contains a discrete component. An anomaly in the spectrum near eigenvalue 0 for connectivity close to c is observed. We develop recursion relations t o compute the moments as explicit polynomials in pN. Their growth is slow e nough so that they determine the spectrum. The extension of our methods to the Laplacian matrix is given in Appendix.