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 <>
Submitted on : Wednesday, August 12, 2015 - 3:51:48 PM
Last modification on : Wednesday, May 10, 2017 - 5:39:18 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:40:14 AM

File

dmAD0121.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184031, version 1

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. ⟨hal-01184031⟩

Share

Metrics

Record views

108

Files downloads

584