A Central Limit Theorem for Almost Local Additive Tree Functionals

0510355 - ÚI 2021 RIV US eng J - Journal Article
Ralaivaosaona, D. - Šileikis, Matas - Wagner, S.
A Central Limit Theorem for Almost Local Additive Tree Functionals.
Algorithmica. Roč. 82, č. 3 (2020), s. 642-679. ISSN 0178-4617. E-ISSN 1432-0541
R&D Projects: GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : Galton–Watson trees * Additive functional * Almost local * Central limit theorem
OECD category: Pure mathematics
Impact factor: 0.791, year: 2020
Method of publishing: Limited access
http://dx.doi.org/10.1007/s00453-019-00622-4

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. Svante 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 procedure that was studied by Hackl, Heuberger, Kropf, and Prodinger.
Permanent Link: http://hdl.handle.net/11104/0300877