A central limit theorem for almost local additive tree functionals

DOI10.1007/S00453-019-00622-4zbMATH Open1446.60011arXiv1810.00467OpenAlexW3101721269MaRDI QIDQ2292863FDOQ2292863

Authors: Dimbinaina Ralaivaosaona, M. Şileikis, Stephan Wagner 

Publication date: 6 February 2020

Published in: Algorithmica (Search for Journal in Brave)

Abstract: An additive functional of a rooted tree is a functional that can be calculated recursively as the sum of the values of the functional over the branches, plus a certain toll function. Janson recently proved a central limit theorem for additive functionals of conditioned Galton-Watson trees under the assumption that the toll function is local, i.e. only depends on a fixed neighbourhood of the root. We extend his result to functionals that are "almost local" in a certain sense, thus covering a wider range of functionals. The notion of almost local functional intuitively means that the toll function can be approximated well by considering only a neighbourhood of the root. Our main result is illustrated by several explicit examples including natural graph theoretic parameters such as the number of independent sets, the number of matchings, and the number of dominating sets. We also cover a functional stemming from a tree reduction process that was studied by Hackl, Heuberger, Kropf, and Prodinger.

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

Recommendations

• A central limit theorem for additive functionals of increasing trees
• Central limit theorems for additive functionals and fringe trees in tries
• Central limit theorems for additive tree parameters with small toll functions
• A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees
• On central limit theory for random additive functions under weak dependence restrictions
• scientific article; zbMATH DE number 431868
• Functional central limit theorem for random walks in random environment defined on regular trees
• Limiting distributions for additive functionals on Catalan trees

zbMATH Keywords

central limit theoremadditive functionalGalton-Watson treesalmost local

Mathematics Subject Classification ID

Trees (05C05) Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Random Trees
• Trees with extremal numbers of dominating sets
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Limit laws for functions of fringe trees for binary search trees and random recursive trees
• Random cutting and records in deterministic and random trees
• Title not available (Why is that?)
• Subdiffusive behavior of random walk on a random cluster
• Twelve countings with rooted plane trees
• Conditional limit theorems for branching processes
• Correlation of Graph‐Theoretical Indices
• Title not available (Why is that?)
• A central limit theorem for additive functionals of increasing trees
• On the number of matchings of a tree
• Central limit theorems for additive tree parameters with small toll functions
• Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees
• Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
• Fringe analysis of plane trees related to cutting and pruning
• Asymptotic normality of almost local functionals in conditioned Galton-Watson trees

Cited In (10)

• Central limit theorems for additive tree parameters with small toll functions
• Limiting distributions for additive functionals on Catalan trees
• Central limit theorems for additive functionals and fringe trees in tries
• Asymptotic normality of almost local functionals in conditioned Galton-Watson trees
• Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees
• The distribution of the number of automorphisms of random trees
• Additive tree functionals with small toll functions and subtrees of random trees
• On general subtrees of a conditioned Galton-Watson tree
• A central limit theorem for additive functionals of increasing trees
• A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees

This page was built for publication: A central limit theorem for almost local additive tree functionals

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