The largest eigenvalue of sparse random graphs

被引：113
作者：
Krivelevich, M [1 ]
Sudakov, B
机构：
[1] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Dept Math, IL-69978 Tel Aviv, Israel
[2] Princeton Univ, Dept Math, Princeton, NJ 08544 USA
[3] Inst Adv Study, Princeton, NJ 08540 USA
来源：
COMBINATORICS PROBABILITY & COMPUTING | 2003年 / 12卷 / 01期
关键词：
D O I：
10.1017/S0963548302005424
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We prove that, for all values of the edge probability p(n), the largest eigenvalue of the random graph G(n, p) satisfies almost surely lambda(1) (G) = (1 + o(1)) max{rootDelta, np}, where Delta is the maximum degree of G, and the o(1) term tends to zero as max{rootDelta, np} tends to infinity.
引用
收藏
页码：61 / 72
页数：12
相关论文
共 13 条
[1]   Spectral techniques in graph algorithms [J].
Alon, N .
LATIN '98: THEORETICAL INFORMATICS, 1998, 1380 :206-215
[2]  
ALON N, IN PRESS ISRAEL J MA
[3]  
ALON N, 1992, PROBABILISTIC METHOD
[4]  
Bollobas B., 2001, CAMBRIDGE STUDIES AD, V73
[5]  
Chung F. R. K., 1997, SPECTRAL GRAPH THEOR
[6]  
Cvetkovic D., 1995, Spectra of Graphs-Theory and Application, V3rd ed.
[7]   THE EIGENVALUES OF RANDOM SYMMETRIC-MATRICES [J].
FUREDI, Z ;
KOMLOS, J .
COMBINATORICA, 1981, 1 (03) :233-241
[8]  
Janson S, 2000, WIL INT S D, DOI 10.1002/9781118032718
[9]   Sparse random matrices: Spectral edge and statistics of rooted trees [J].
Khorunzhy, A .
ADVANCES IN APPLIED PROBABILITY, 2001, 33 (01) :124-140
[10]  
KHORUNZHY A, MATHPH0009028
12