Empirical Distributions of Laplacian Matrices of Large Dilute Random Graphs

We study the spectral properties of the Laplacian matrices and the normalized Laplacian matrices of the Erdös–Rényi random graph G(n, p n ) for large n. Although the graph is simple, we discover some interesting behaviors of the two Laplacian matrices. In fact, under the dilute case, that is, p n ∈ (0, 1) and np n → ∞, we prove that the empirical distribution of the eigenvalues of the Laplacian matrix converges to a deterministic distribution, which is the free convolution of the semi-circle law and N(0, 1). However, for its normalized version, we prove that the empirical distribution converges to the semi-circle law.