A central limit theorem for almost local additive tree functionals

0494601 - ÚI 2019 US eng V - Výzkumná zpráva
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].
Grant CEP: GA ČR GJ16-07822Y
Institucionální podpora: RVO:67985807
Klíčová slova: Galton-Watson trees * additive functional * almost local * central limit theorem
Obor OECD: 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.
Trvalý link: http://hdl.handle.net/11104/0287713