4.0 Article

Spectra of Large Random Trees

期刊

JOURNAL OF THEORETICAL PROBABILITY
卷 25, 期 3, 页码 613-654

出版社

SPRINGER/PLENUM PUBLISHERS
DOI: 10.1007/s10959-011-0360-9

关键词

Eigenvalue; Random matrix; Random graph; Adjacency matrix; Graph Laplacian; Interlacing; Preferential attachment; Recursive random tree; Yule tree; Local weak convergence; Probability fringe convergence; Maximal matching; Karp-Sipser algorithm; Branching process; Isospectral; Exchange property

资金

  1. NSF [DMS-0704159, DMS-0405778, DMS-0907630]
  2. PIMS
  3. NSERC Canada

向作者/读者索取更多资源

We analyze the eigenvalues of the adjacency matrices of a wide variety of random trees. Using general, broadly applicable arguments based on the interlacing inequalities for the eigenvalues of a principal submatrix of a Hermitian matrix and a suitable notion of local weak convergence for an ensemble of random trees that we call probability fringe convergence, we show that the empirical spectral distributions for many random tree models converge to a deterministic (model-dependent) limit as the number of vertices goes to infinity. Moreover, the masses assigned by the empirical spectral distributions to individual points also converge in distribution to constants. We conclude for ensembles such as the linear preferential attachment models, random recursive trees, and the uniform random trees that the limiting spectral distribution has a set of atoms that is dense in the real line. We obtain lower bounds on the mass assigned to zero by the empirical spectral measures via the connection between the number of zero eigenvalues of the adjacency matrix of a tree and the cardinality of a maximal matching on the tree. In particular, we employ a simplified version of an algorithm due to Karp and Sipser to construct maximal matchings and understand their properties. Moreover, we show that the total weight of a weighted matching is asymptotically equivalent to a constant multiple of the number of vertices when the edge weights are independent, identically distributed, nonnegative random variables with finite expected value, thereby significantly extending a result obtained by Aldous and Steele in the special case of uniform random trees. We greatly generalize a celebrated result obtained by Schwenk for the uniform random trees by showing that if any ensemble converges in the probability fringe sense and a very mild further condition holds, then, with probability converging to one, the spectrum of a realization is shared by at least one other (nonisomorphic) tree. For the linear preferential attachment model with parameter a >-1, we show that for any fixed k, the k largest eigenvalues jointly converge in distribution to a nontrivial limit when rescaled by , where gamma (a) =a+2 is the Malthusian rate of growth parameter for an associated continuous-time branching process.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.0
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据