Additive functionals of d-ary increasing trees

zbMATH Open1411.68041arXiv1605.03918MaRDI QIDQ4632497FDOQ4632497

Authors: Dimbinaina Ralaivaosaona, Stephan Wagner 

Publication date: 29 April 2019

Abstract: A tree functional is called additive if it satisfies a recursion of the form $F(T)=su{m}_{j=1}^{k}F(B_j)+f(T)$, where $B_1,ldots,B_k$ are the branches of the tree $T$ and $f(T)$ is a toll function. We prove a general central limit theorem for additive functionals of $d$-ary increasing trees under suitable assumptions on the toll function. The same method also applies to generalised plane-oriented increasing trees (GPORTs). One of our main applications is a log-normal law that we prove for the size of the automorphism group of $d$-ary increasing trees, but many other examples (old and new) are covered as well.

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

Recommendations

• A central limit theorem for additive functionals of increasing trees
• A central limit theorem for almost local additive tree functionals
• Central limit theorems for additive tree parameters with small toll functions
• Additive tree functionals with small toll functions and subtrees of random trees
• Limiting distributions for additive functionals on Catalan trees

zbMATH Keywords

central limit theoremautomorphismsrandom treesincreasing treesadditive tree functional

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Analysis of algorithms (68W40) Data structures (68P05) Combinatorial probability (60C05)

Cited In (6)

• Central limit theorems for additive tree parameters with small toll functions
• Limiting distributions for additive functionals on Catalan trees
• Asymptotic normality of almost local functionals in conditioned Galton-Watson trees
• Additive tree functionals with small toll functions and subtrees of random trees
• A decreasing rearrangement for functions on homogeneous trees
• A central limit theorem for additive functionals of increasing trees

This page was built for publication: Additive functionals of $d$-ary increasing trees

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