Sparse random graphs: Eigenvalues and eigenvectors. Issue 1 (5th March 2012)

• Record Type: Journal Article
• Authors: Tran, Linh V.; Vu, Van H.; Wang, Ke
• Is Part Of: Random structures & algorithms. Volume 42:Issue 1(2013)
• Page Start: 110
• Page End: 134
• Publication Date: 2012-03-05
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20406
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>In this paper, we prove the semi‐circular law for the eigenvalues of regular random graph <italic>G</italic>_{<italic>n</italic>, <italic>d</italic>} in the case <italic>d</italic> →<italic>∞</italic>, complementing a previous result of McKay for fixed <italic>d</italic>. We also obtain a upper bound on the infinity norm of eigenvectors of Erdős–Rényi random graph <italic>G</italic>(<italic>n</italic>, <italic>p</italic>), answering a question raised by Dekel–Lee–Linial. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012</p> </abstract>