Spectral Analysis Of Several Random Graphs

Random graph theory was founded by Erdos and Renyi in 1950s.It mainly studies the relationships between the spectral property and the structural property of graphs with the tools of probability theory and stochastic process theory.Spectral random graph theory is an important part of random graph theory.It mainly focuses on the limiting behavior of the eigenvalues and eigenvectors of various random matrices associated with random graphs.It not only has important theoretical value but also has extensive applications in many fields such as physics and chemistry.In this dissertation,based on the random multipartite graph model,the random mixed graph model and the random oriented graph model,the spectral properties of several corresponding random matrices are studied.The main research results are as follows:1.The spectra of random multipartite graphs and the relationship between some invariants and the spectra of graphs are studied.By analyzing the the limiting behavior of the spectra of random symmetric matrices,we estimate the eigenvalues of the Laplacian matrix of random multipartite graphs,and establish asymptotic lower and upper bounds for the Laplacian energy,the Laplacian Estrada index and the von Neumann entropy of random multipartite graphs respectively.2.The spectral properties of Hermitian adjacency matrices and normalized Hermitian Laplacian matrices of random mixed graphs are studied.The concept of the random mixed graph model is proposed for the first time.We prove that the limiting spectral distributions of Hermitian adjacency matrices and normalized Hermitian Laplacian matrices of random mixed graphs are Wigner's semicircle law.The asymptotic expression of the Hermitian energy of random mixed graphs is given by the limiting spectral distribution of Hermitian adjacency matrices.Moreover,the asymptotic expression of the largest eigenvalue of the Hermitian adjacency matrix and the asymptotic bounds of other eigenvalues are obtained,and then the asymptotic estimation of the Laplacian spectral moment of random mixed graphs is given.3.The spectra of Hermitian adjacency matrices and normalized Hermitian Laplacian matrices of general random mixed graphs are studied.We establish a stronger version of Bernstein's inequality on random matrices,and present a new probability inequality for sums of independent random Hermitian matrices.Using this probability inequality,we estimate the asymptotic bound of the spectral radius of the Hermitian adjacency matrix,and give an approximate estimation of the eigenvalues of the normalized Hermitian Laplacian matrix.4.The spectral radii of skew adjacency matrices and skew Randic matrices of random oriented graphs are studied.We express the skew adjacency matrix and the skew Randic matrix by sums of independent random matrices,and then establish asymptotic upper bounds for the spectral radii of skew adjacency matrices and skew Randic matrices of random oriented graphs by a probability inequality for sums of independent random matrices.The above research results reveal the spectral properties of random multipartite graphs,random mixed graphs and random oriented graphs.It not only enriches the theoretical research of random graphs,but also extends the important results such as probability inequalities and Wigner's semicircle law in random matrix theory.