# Non-crossing trees revisited: cutting down and spanning subtrees

Abstract : Here we consider two parameters for random non-crossing trees: $\textit{(i)}$ the number of random cuts to destroy a size-$n$ non-crossing tree and $\textit{(ii)}$ the spanning subtree-size of $p$ randomly chosen nodes in a size-$n$ non-crossing tree. For both quantities, we are able to characterise for $n → ∞$ the limiting distributions. Non-crossing trees are almost conditioned Galton-Watson trees, and it has been already shown, that the contour and other usually associated discrete excursions converge, suitable normalised, to the Brownian excursion. We can interpret parameter $\textit{(ii)}$ as a functional of a conditioned random walk, and although we do not have such an interpretation for parameter $\textit{(i)}$, we obtain here limiting distributions, that are also arising as limits of some functionals of conditioned random walks.
Keywords :
Type de document :
Communication dans un congrès
Cyril Banderier and Christian Krattenthaler. Discrete Random Walks, DRW'03, 2003, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), pp.265-276, 2003, DMTCS Proceedings
Domaine :

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

https://hal.inria.fr/hal-01183922
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 09:06:36
Dernière modification le : jeudi 11 mai 2017 - 01:02:54
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:37:09

### Fichier

dmAC0125.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01183922, version 1

### Citation

Alois Panholzer. Non-crossing trees revisited: cutting down and spanning subtrees. Cyril Banderier and Christian Krattenthaler. Discrete Random Walks, DRW'03, 2003, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03), pp.265-276, 2003, DMTCS Proceedings. 〈hal-01183922〉

### Métriques

Consultations de la notice

## 52

Téléchargements de fichiers