SPARSE REGULAR RANDOM GRAPHS: SPECTRAL DENSITY AND EIGENVECTORS

被引：58

作者：

Dumitriu, Ioana ^{[1
]}

Pal, Soumik ^{[1
]}

机构：

[1] Univ Washington, Seattle, WA 98195 USA

来源：

ANNALS OF PROBABILITY | 2012年 / 40卷 / 05期

基金：

美国国家科学基金会;

关键词：

Random regular graphs; spectral distribution; universality; semicircle law; LOCAL EIGENVALUE STATISTICS; LARGE RANDOM MATRICES; BULK UNIVERSALITY; SEMICIRCLE LAW; ENSEMBLES; EDGE; DELOCALIZATION; FLUCTUATIONS; CONVERGENCE;

D O I：

10.1214/11-AOP673

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We examine the empirical distribution of the eigenvalues and the eigenvectors of adjacency matrices of sparse regular random graphs. We find that when the degree sequence of the graph slowly increases to infinity with the number of vertices, the empirical spectral distribution converges to the semicircle law. Moreover, we prove concentration estimates on the number of eigenvalues over progressively smaller intervals. We also show that, with high probability, all the eigenvectors are delocalized.

引用

页码：2197 / 2235

页数：39

共 50 条

[1] Convergence of the density of states and delocalization of eigenvectors on random regular graphs
Geisinger, Leander
JOURNAL OF SPECTRAL THEORY, 2015, 5 (04) : 783 - 827
[2] ON THE ALMOST EIGENVECTORS OF RANDOM REGULAR GRAPHS
Backhausz, Agnes
Szegedy, Balazs
ANNALS OF PROBABILITY, 2019, 47 (03): : 1677 - 1725
[3] Sparse random graphs: Eigenvalues and eigenvectors
Tran, Linh V.
Vu, Van H.
Wang, Ke
RANDOM STRUCTURES & ALGORITHMS, 2013, 42 (01) : 110 - 134
[4] SPARSE EIGENVECTORS OF GRAPHS
Teke, Oguzhan
Vaidyanathan, P. P.
2017 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2017, : 3904 - 3908
[5] The spectral gap of random regular graphs
Sarid, Amir
RANDOM STRUCTURES & ALGORITHMS, 2023, 63 (02) : 557 - 587
[6] Regular pairs in sparse random graphs I
Kohayakawa, Y
Rödl, V
RANDOM STRUCTURES & ALGORITHMS, 2003, 22 (04) : 359 - 434
[7] THE SPECTRAL GAP OF DENSE RANDOM REGULAR GRAPHS
Tikhomirov, Konstantin
Youssef, Pierre
ANNALS OF PROBABILITY, 2019, 47 (01): : 362 - 419
[8] Spectral classes of regular, random, and empirical graphs
Gu, Jiao
Jost, Juergen
Liu, Shiping
Stadler, Peter F.
LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 489 : 30 - 49
[9] Spectral techniques applied to sparse random graphs
Feige, U
Ofek, E
RANDOM STRUCTURES & ALGORITHMS, 2005, 27 (02) : 251 - 275
[10] Braess's Paradox for the Spectral Gap in Random Graphs and Delocalization of Eigenvectors
Eldan, Ronen
Racz, Miklos Z.
Schramm, Tselil
RANDOM STRUCTURES & ALGORITHMS, 2017, 50 (04) : 584 - 611

← 1 2 3 4 5 →