期刊
ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES
卷 56, 期 4, 页码 2307-2328出版社
INST MATHEMATICAL STATISTICS-IMS
DOI: 10.1214/19-AIHP1032
关键词
Random matrices; Sparse matrices; Eigenvalue degeneracy; Random graphs; Graph isomorphism
资金
- National Science Foundation [1702533]
- NSF [DMS 1307797]
- AFORS [FA9550-12-1-0083]
- Division Of Mathematical Sciences
- Direct For Mathematical & Physical Scien [1702533] Funding Source: National Science Foundation
Let M-n be a class of symmetric sparse random matrices, with independent entries M-ij = delta(ij)xi(ij) for i <= j. delta(ij) are i.i.d. Bernoulli random variables taking the value 1 with probability p >= n(-1+delta) for any constant delta > 0 and xi(ij) are i.i.d. centered, subgaussian random variables. We show that with high probability this class of random matrices has simple spectrum (i.e. the eigenvalues appear with multiplicity one). We can slightly modify our proof to show that the adjacency matrix of a sparse Erdos-Renyi graph has simple spectrum for n(-1+delta) <= p <= 1-n(-1+delta). These results are optimal in the exponent. The result for graphs has connections to the notorious graph isomorphism problem.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据