Spectra of large random trees (Q715739): Difference between revisions
From MaRDI portal
Normalize DOI. |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1007/S10959-011-0360-9 / rank | |||
Property / DOI | |||
Property / DOI: 10.1007/S10959-011-0360-9 / rank | |||
Normal rank |
Latest revision as of 01:39, 10 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Spectra of large random trees |
scientific article |
Statements
Spectra of large random trees (English)
0 references
1 November 2012
0 references
In this paper, the authors study the spectral distributions of adjacency matrices for ensemble of large random trees. A general and powerful technique based on probability fringe convergence is introduced. It is shown that the empirical spectral distributions for random tree models, such as random recursive tree, linear preferential attachment tree, uniform random rooted unordered labeled tree and random binary tree, converge to deterministic limits as the number of vertices goes to infinity. Some of the key techniques used include the interlacing inequalities, method of moments, Karp-Sipser algorithm and branching process. Amongst other results, the authors show that the \(k\) largest eigenvalues for the linear preferential attachment model jointly converge in distribution to a nontrivial limit, where the rate of convergence is related to the Malthusian parameter for a continuous-time branching process.
0 references
eigenvalue
0 references
random matrix
0 references
random graph
0 references
adjacency matrix
0 references
graph Laplacian
0 references
interlacing
0 references
preferential attachment
0 references
recursive random tree
0 references
Yule tree
0 references
local weak convergence
0 references
probability fringe convergence
0 references
maximal matching
0 references
Karp-Sipser algorithm
0 references
branching process
0 references
isospectral
0 references
exchange property
0 references
0 references
0 references
0 references