Low eigenvalues of Laplacian matrices of large random graphs

• 成果类型: Article
• 署名作者: Jiang, Tiefeng
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-011-0357-4
• 发表日期: 2012
• 页码: 671-690
• 关键词: markov

摘要

For each n a parts per thousand yen 2, let A (n) = (xi (ij) ) be an n x n symmetric matrix with diagonal entries equal to zero and the entries in the upper triangular part being independent with mean mu (n) and standard deviation sigma (n) . The Laplacian matrix is defined by . In this paper, we obtain the laws of large numbers for lambda (n-k) (Delta (n) ), the (k + 1)-th smallest eigenvalue of Delta (n) , through the study of the order statistics of weakly dependent random variables. Under certain moment conditions on xi (ij) 's, we prove that, as n -> infinity, (i) lambda(n-k)(Delta(n))-n mu(n)/sigma(n)root n logn -> -root 2 a.s. for any k >= 1. Further, if {Delta (n) ; n >= 2} are independent with mu (n) = 0 and sigma (n) = 1, then, (ii) the sequence is dense in for any {lambda(n-k)(Delta(n))/root n; n >= 2} is dense in [-root 2 + 2(k + 1)(-1), -root 2] a.s. for any k >= 0. In particular, (i) holds for the Erdos-R,nyi random graphs. Similar results are also obtained for the largest eigenvalues of Delta (n) .