Spectra of large random trees

DOI10.1007/S10959-011-0360-9zbMATH Open1255.05114arXiv0903.3589OpenAlexW2055033386MaRDI QIDQ715739FDOQ715739

Authors: Shankar Bhamidi, Steven Neil Evans, Arnab Sen 

Publication date: 1 November 2012

Published in: Journal of Theoretical Probability (Search for Journal in Brave)

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 $a>-1$, we show that the suitably rescaled $k$ largest eigenvalues converge jointly.

Full work available at URL: https://arxiv.org/abs/0903.3589

Recommendations

• Resolvent of large random graphs
• Spectral distributions of adjacency and Laplacian matrices of random graphs
• Spectra of large diluted but bushy random graphs
• Spectral atoms of unimodular random trees
• scientific article; zbMATH DE number 2046064

zbMATH Keywords

random matrixrandom graphadjacency matrixeigenvaluebranching processlocal weak convergencepreferential attachmentexchange propertygraph LaplacianinterlacingKarp-Sipser algorithmmaximal matchingisospectralprobability fringe convergencerecursive random treeYule tree

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cites Work

• Log-gases and random matrices.
• Title not available (Why is that?)
• Markov Chains
• Interlacing eigenvalues and graphs
• Title not available (Why is that?)
• Eigenspaces of graphs
• General branching processes as Markov fields
• Orthogonal polynomials and random matrices: a Riemann-Hilbert approach.
• Graph theory with applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Maximum Degree of the Barabási–Albert Random Tree
• Title not available (Why is that?)
• Recent results in the theory of graph spectra
• Convergence rate of expected spectral distributions of large random matrices. I: Wigner matrices
• 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
• Asymptotic fringe distributions for general families of random trees
• The continuum random tree. I
• Resolvent of large random graphs
• Title not available (Why is that?)
• Spectra of random graphs with given expected degrees
• Harmonic analysis of finite lamplighter random walks
• Spectral computations on lamplighter groups and Diestel-Leader graphs
• Eigenvalue interlacing and weight parameters of graphs
• Eigenvalues of random power law graphs
• Random trees and general branching processes
• The growth and composition of branching populations
• On the spectra of some weighted rooted trees and applications
• Spectra of weighted generalized Bethe trees joined at the root
• On the spectrum of lamplighter groups and percolation clusters
• The spectra of the adjacency matrix and Laplacian matrix for some balanced trees
• Title not available (Why is that?)
• An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree
• On the spectra of certain rooted trees
• Robustness and Vulnerability of Scale-Free Random Graphs
• On the kernel of tree incidence matrices
• High Degree Vertices and Eigenvalues in the Preferential Attachment Graph
• The spectra of some trees and bounds for the largest eigenvalue of any tree
• The stable doubly infinite pedigree process of supercritical branching populations
• The rank of diluted random graphs
• Graphs and Hermitian matrices: eigenvalue interlacing
• Almost all trees share a complete set of immanantal polynomials
• High degree vertices and eigenvalues in the preferential attachment graph
• The spectra of a graph obtained from copies of a generalized Bethe tree

Cited In (18)

• Spectrum of partial automorphisms of regular 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
• Title not available (Why is that?)
• On the distribution of eigenvalues of increasing trees
• Sparse regular random graphs: spectral density and eigenvectors
• Community modulated recursive trees and population dependent branching processes
• Special integral variation of trees
• 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
• Spectral properties of partial automorphisms of a binary rooted tree

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)