Spectra of large random trees (Q715739): Difference between revisions

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.