Some Spectral Properties Of Matrices In Random Graph

Some Spectral Properties of Matrices in Random GraphThe random graph theory has a long history, it was first founded by Erdos and Renyi in 1950s. In the present information age, random graph theory has more and more applications, specially, in many real networks, for example, internet graph, bi-ological networks and other graph representing relations in massive data sets. Now this field is studied a lot. We can associate many types of matrices to a given graph, but adjacent matrix and Laplacian matrix are most studied, we call the spectra of the corresponding random matrices as the spectra of the random graph. Spectra of different matrices yield different but complementary information about the graph. The spectrum of the adjacent matrix is useful for various enumeration problems. The de-terminant of cofactor of Laplacian matrix is equal to the number of spanning trees in a graph. The.eigenvalues of normalized laplacian relate well to many key graph invariants, for example, the Cheeger constant and discrepancy of graph.In this thesis we will use the method from random matrix theory to study the spectrum properties of matrices mentioned above. The adjacent matrix of a graph is a n x n symmetric matrix having following form where are independent random variables,letμn= holds'and we have where then we proved that the empirical spectral distribution converges to the famous Wigner semi-circle law almost surely in the section 2 of Chapter l,where and are the eigenvalues of An.Ifξij(n) satisfying then we get that the empirical spectral distribution FAn/(?) of matrix An/(?) also converges to semicircle law almost surely. The results obtained by Furedi and Komlos in[36]for pn=p is a constant are our immediately corollary.If there exist some kind of relation betweenμn andσn, then we can obtain the large number property for the largest eigenvalue and spectrum norm of adjacent matrix An,for details,see theorem 2.2 of section 1.2 from Chapter 1.For a given random graph,its Laplacian matrix is where{ξ1j(n)}are defined as before.If nolds for some p>4,then we proved that the empirical spectral distribution Fn(x)of the Laplacian matrix(△n-μnIn)/(?) converges to the free convolution of semicircle law and standard normal distributionγM almost surely in section 1.3 from Chapter 1,where andγM does not depend on and is a probability measure having smooth,bounded density and unbounded support.As for the adjacent matrix,if there exist some kind of relation betweenμn andσn,we obtained that the largest eigen-value and spectrum norm of△n have properties of large numbers.Under the condition that{△1,△2,...,△n,...}are independent,we get a interesting result:Let denote the largest eigenvalue of△n,then the sequence is dense in interval[(?),2]almost surely if This property does not holds for general random matrix.All the conclusions above comes from the author's pa-per"Spectral Distributions of Adj acency and Laplacian Matrices of Random Graphs" which is accepted by"The Annals of Applied Probability". In Chapter 2 we mainly study the spectra of a special random graph:the ran-dom graph with given expected degree sequence. Let G=(V(G),E(G)), V(G)= {v1,...,vn} are the vertices of G. For a nonnegative w=(ω1,...,ωn),every two ver-tices (vi, vj) form a edge of G with probabilityωiWjρ,and all the forming of edges are in-dependent, her For convenience, we call (vi, vj) are connected, if (vi, vj) is a edge of G, write it as vi～vj. There we always assume that in order to ensure thatωiωjρis a probability for all i,j. Let d(vi) denote the num-ber of vertex connected with vi, then we call d(vi) the degree of vi. It is easy to see that Ed(vi)=ωi, for this reason G(w) is called the random graph with given expected degree sequence. The classical Erdos-Renyi random graph Gn,P is also a random graph with given expected degree sequence with the expected degree sequence (ω1,...,ωn)＝(np,...,np).For this random graph we mainly study the following three types of matrix asso-ciated with it:1 The Adjacent matrix An is symmetric matrix and{aij,1≤i≤j≤n}have distribution from the definition we can see that:aij=1 if (vi,vj) is a edge of, otherwise aij=1.2 The combinatorial Laplacian matrix Ln, where An is the adjacent matrix, Dn is n x n diagonal matrix, its element in (i,i) is the degree d(vi) of vi.3 The normalized Laplacian matrix (?)n, where In is n×n identity matrix,An, Dn is defined as before.The empirical spectral distribution of the combinatorial Laplacian matrix con-verges to a mixed points mass distribution; the empirical spectral distribution of the centered combinatorial Laplacian matrix converges free convolution of semicircle law and normal distribution. In section 2.3 we also proved that the scaled second samllest eigenvalues of normalized Laplacian matrix converges to a constant under a appropri-ate condition on the degree sequence. The empirical spectral distribution of normalized Laplacian matrix converges to different probability distribution under different condi-tion on the degree sequence, some of those probability measures are semicircle law, some of those are free convolution of semicircle law and other fixed probability mea-sures, for details, see theorem 3.4 in Chapter 2. The empirical spectral distribution of the scaled adjacent matrix behaves like the empirical spectral distribution of the scaled normalized Laplacian matrix, see theorem 4.1 in Chapter 2. The emergence of the free convolution comes from the fact that the scaled normalized Laplacian matrix and the scaled adjacent matrix have same limiting empirical spectral distribution as random matrix where Gni, Gn2 are independent matrix and Gn1 is well known Gaussian orthogonal ensemble. By the free probability theory we know that the empirical spectral distribution of random matrix converges to free convolution of limiting empirical spectral distribution of In Chapter 2 we introduce those results in details.