2016/06/28 by Gittenberger, Bernhard, Jin, Emma Yu, Wallner, Michael
#05A16 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1606.08769
Panagiotou and Stufler (arXiv:1502.07180v2) recently proved one important fact on their way to establish the scaling limits of random Pólya trees: a uniform random Pólya tree of size n consists of a conditioned critical Galton-Watson tree Cn and many small forests, where with probability tending to one as n tends to infinity, any forest Fn(v), that is attached to a node v in Cn, is maximally of size \vert Fn(v)\vert=O(log n). Their proof used the framework of a Boltzmann sampler and deviation inequalities. In this paper, first, we employ a unified framework in analytic combinatorics to prove this fact with additional improvements on the bound of \vert Fn(v)\vert, namely \vert Fn(v)\vert=Θ(log n). Second, we give a combinatorial interpretation of the rational weights of these forests and the defining substitution process in terms of automorphisms associated to a given Pólya tree. Finally, we derive the limit probability that for a random node v the attached forest Fn(v) is of a given size.