A Central Limit Theorem for Almost Local Additive Tree Functionals

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.