Skip to Main content Skip to Navigation
Conference papers

Pattern distribution in various types of random trees

Abstract : Let $\mathcal{T}_n$ denote the set of unrooted unlabeled trees of size $n$ and let $\mathcal{M}$ be a particular (finite) tree. Assuming that every tree of $\mathcal{T}_n$ is equally likely, it is shown that the number of occurrences $X_n$ of $\mathcal{M}$ as an induced sub-tree satisfies $\mathbf{E} X_n \sim \mu n$ and $\mathbf{V}ar X_n \sim \sigma^2 n$ for some (computable) constants $\mu > 0$ and $\sigma \geq 0$. Furthermore, if $\sigma > 0$ then $(X_n - \mathbf{E} X_n) / \sqrt{\mathbf{V}ar X_n}$ converges to a limiting distribution with density $(A+Bt^2)e^{-Ct^2}$ 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 $T_n$ then the limiting distribution is always normal. Similar results can be proved for planar, labeled and simply generated trees.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184031
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, August 12, 2015 - 3:51:48 PM
Last modification on : Wednesday, October 13, 2021 - 7:58:04 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:40:14 AM

File

dmAD0121.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Gerard Kok. Pattern distribution in various types of random trees. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.223-230, ⟨10.46298/dmtcs.3359⟩. ⟨hal-01184031⟩

Share

Metrics

Record views

42

Files downloads

377