DMTCS Proceedings, 2005 International Conference on Analysis of Algorithms

Font Size:  Small  Medium  Large

Pattern distribution in various types of random trees

Gerard Kok


Let Tn denote the set of unrooted unlabeled trees of size n and let Mk be a particular (finite) tree. Assuming that every tree of Tn is equally likely, it is shown that the number of occurrences Xn of Mk as an induced sub-tree satisfies E Xn ∼µn and Var Xn ∼σ2 n for some (computable) constants µ> 0 and σ≥0. Furthermore, if σ>0 then (Xn - E Xn)/√Var Xn converges to a limiting distribution with density (A+Bt2)e-Ct2 for some constants A,B,C. However, in all cases in which we were able to calculate these constants, we obtained B=0 and thus a normal distribution. Further, if we consider planted or rooted trees instead of Tn then the limiting distribution is always normal. Similar results can be proved for planar, labeled and simply generated trees.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional