Spectra of Large Random Trees

Shankar Bhamidi (), Steven N. Evans () and Arnab Sen ()
Additional contact information
Shankar Bhamidi: The University of British Columbia
Steven N. Evans: University of California at Berkeley
Arnab Sen: University of California at Berkeley

Journal of Theoretical Probability, 2012, vol. 25, issue 3, 613-654

Abstract: Abstract 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 $n^{1/2\gamma_{a}}$ , where γ a =a+2 is the Malthusian rate of growth parameter for an associated continuous-time branching process.

Keywords: 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; 60C05; 05C80; 90B15 (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10959-011-0360-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:25:y:2012:i:3:d:10.1007_s10959-011-0360-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-011-0360-9

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().