On the distribution of eigenvalues of increasing trees

DOI10.1016/J.DISC.2023.113762MaRDI QIDQ6184541zbMATH OpenFDO

Authors Kenneth Dadedzi, Stephan Wagner

Publication date 25 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

central limit theoremeigenvaluesrecursive treebinary increasing treeadditive parameter

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Combinatorial probability (60C05)

Abstract: We prove that the multiplicity of a fixed eigenvalue $alpha$ in a random recursive tree on $n$ vertices satisfies a central limit theorem with mean and variance asymptotically equal to $m{u}_{alpha}n$ and $sigm{a}_{alpha}^{2}n$ respectively. It is also shown that $m{u}_{alpha}$ and $sigm{a}_{alpha}^2$ are positive for every totally real algebraic integer. The proofs are based on a general result on additive tree functionals due to Holmgren and Janson. In the case of the eigenvalue $0$, the constants $m{u}_0$ and $sigm{a}_0^2$ can be determined explicitly by means of generating functions. Analogous results are also obtained for Laplacian eigenvalues and binary increasing trees.

Recommendations

• Spectra of large random trees
• A central limit theorem for additive functionals of increasing trees
• Asymptotic degree distribution in random recursive trees
• On the distribution of distances between specified nodes in increasing trees
• On the degree distribution of the nodes in increasing trees

Cites work

• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 3504991 (Why is no real title available?)
• scientific article; zbMATH DE number 2018401 (Why is no real title available?)
• scientific article; zbMATH DE number 6026126 (Why is no real title available?)
• scientific article; zbMATH DE number 3411062 (Why is no real title available?)
• A central limit theorem for additive functionals of increasing trees
• A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
• An introduction to random matrices
• An introduction to the theory of graph spectra
• Analytic combinatorics
• Asymptotic fringe distributions for general families of random trees
• Central limit theorems for additive tree parameters with small toll functions
• Every totally real algebraic integer is a tree eigenvalue
• Level of nodes in increasing trees revisited
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy
• On the distribution of the roots of certain symmetric matrices
• On the independence number of some random trees
• On the kernel of tree incidence matrices
• Probability: a graduate course
• Random Trees
• Spectra of large random trees
• Spectral analysis of large dimensional random matrices
• Spectral atoms of unimodular random trees
• The rank of diluted random graphs

This page was built for publication: On the distribution of eigenvalues of increasing trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6184541)