On the distribution of eigenvalues of increasing trees

DOI10.1016/J.DISC.2023.113762arXiv2208.05575MaRDI QIDQ6184541FDOQ6184541

Authors: Kenneth Dadedzi, Stephan Wagner 

Publication date: 25 January 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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)

Cites Work

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

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)