A central limit theorem for almost local additive tree functionals

0494601 - ÚI 2019 US eng V - Research Report
Ralaivaosaona, D. - Šileikis, Matas - Wagner, S.
A central limit theorem for almost local additive tree functionals.
Cornell University, 2018. 28 s. arXiv.org e-Print archive, arXiv:1810.00467 [math.CO].
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
https://arxiv.org/abs/1810.00467

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.
Permanent Link: http://hdl.handle.net/11104/0287713