# 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.
Keywords :
Type de document :
Communication dans un congrès
Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.223-230, 2005, DMTCS Proceedings
Domaine :

Littérature citée [13 références]

https://hal.inria.fr/hal-01184031
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 15:51:48
Dernière modification le : mercredi 10 mai 2017 - 17:39:18
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:40:14

### Fichier

Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184031, version 1

### Citation

Gerard Kok. Pattern distribution in various types of random trees. Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.223-230, 2005, DMTCS Proceedings. 〈hal-01184031〉

### Métriques

Consultations de la notice

## 84

Téléchargements de fichiers