Title: The distribution of tree parameters via the martingale CLT
| Speaker: | Mikhail Isaev |
| Affiliation: | Monash University |
| Room: | MC 5479 |
Abstract:
Tree parameters, like pattern or symmetry counts, have been extensively studied in the literature for various random models. It is known, in particular, that many important examples exhibit normal or log-normal limit law. A typical approach relies on the recursive nature of trees and properties of its generating functions. We propose a purely probabilistic argument based on the general theory of Central Limit Theorems for martingales. For a uniform random labelled tree, we find the limiting distribution of tree parameters which are stable (in somesense) with respect to local perturbations of a tree structure. Our results are general enough to get the asymptotical normality of the number of occurrences of any given small pattern and the asymptotical log-normality of the number of automorphisms.