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, we show that the empirical spectral distributions for each of a number of random tree models converge to a deterministic (model dependent) limit as the number of vertices goes to infinity. 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 precise asymptotics on the mass assigned to zero by the empirical spectral measures via the connection with the cardinality of a maximal matching. 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, non-negative random variables with finite expected value. We greatly extend a celebrated result obtained by Schwenk for the uniform random trees by showing that, under mild conditions, with probability converging to one, the spectrum of a realization is shared by at least one other tree. For the the linear preferential attachment model with parameter , we show that the suitably rescaled largest eigenvalues converge jointly.
Recommendations
Cites work
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3711987 (Why is no real title available?)
- scientific article; zbMATH DE number 740754 (Why is no real title available?)
- scientific article; zbMATH DE number 2042286 (Why is no real title available?)
- scientific article; zbMATH DE number 2174437 (Why is no real title available?)
- scientific article; zbMATH DE number 1409903 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- Almost all trees share a complete set of immanantal polynomials
- An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree
- Asymptotic fringe distributions for general families of random trees
- Convergence rate of expected spectral distributions of large random matrices. I: Wigner matrices
- Eigenspaces of graphs
- Eigenvalue interlacing and weight parameters of graphs
- Eigenvalues of random power law graphs
- General branching processes as Markov fields
- Graph theory with applications
- Graphs and Hermitian matrices: eigenvalue interlacing
- Harmonic analysis of finite lamplighter random walks
- High Degree Vertices and Eigenvalues in the Preferential Attachment Graph
- High degree vertices and eigenvalues in the preferential attachment graph
- Interlacing eigenvalues and graphs
- Log-gases and random matrices.
- Markov Chains
- On the kernel of tree incidence matrices
- On the spectra of certain rooted trees
- On the spectra of some weighted rooted trees and applications
- On the spectrum of lamplighter groups and percolation clusters
- Orthogonal polynomials and random matrices: a Riemann-Hilbert approach.
- Random incidence matrices: moments of the spectral density
- Random matrix models and their applications. Based on talks and lectures from the workshop, Berkeley, CA, USA, February 22--26, 1999
- Random trees and general branching processes
- Recent results in the theory of graph spectra
- Resolvent of large random graphs
- Robustness and Vulnerability of Scale-Free Random Graphs
- Spectra of random graphs with given expected degrees
- Spectra of weighted generalized Bethe trees joined at the root
- Spectral computations on lamplighter groups and Diestel-Leader graphs
- The Maximum Degree of the Barabási–Albert Random Tree
- The continuum random tree. I
- The growth and composition of branching populations
- The rank of diluted random graphs
- The spectra of a graph obtained from copies of a generalized Bethe tree
- The spectra of some trees and bounds for the largest eigenvalue of any tree
- The spectra of the adjacency matrix and Laplacian matrix for some balanced trees
- The stable doubly infinite pedigree process of supercritical branching populations
Cited in
(18)- Spectrum of partial automorphisms of regular rooted tree
- Spectral properties of partial automorphisms of a binary rooted tree
- Spectral atoms of unimodular random trees
- Trees with Cantor Eigenvalue Distribution
- Resolvent of large random graphs
- Mean quantum percolation
- Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs
- scientific article; zbMATH DE number 2046064 (Why is no real title available?)
- Sparse regular random graphs: spectral density and eigenvectors
- On the distribution of eigenvalues of increasing trees
- Special integral variation of trees
- Community modulated recursive trees and population dependent branching processes
- The rank of diluted random graphs
- Peculiar spectral statistics of ensembles of trees and star-like graphs
- Spectra of adjacency and Laplacian matrices of inhomogeneous Erdős-Rényi random graphs
- Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves
- Change point detection in network models: preferential attachment and long range dependence
- Co-evolving dynamic networks
This page was built for publication: Spectra of large random trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q715739)
