Non-crossing trees revisited: cutting down and spanning subtrees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2003

Non-crossing trees revisited: cutting down and spanning subtrees

Résumé

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.
Fichier principal
Vignette du fichier
dmAC0125.pdf (150.33 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01183922 , version 1 (12-08-2015)

Identifiants

Citer

Alois Panholzer. Non-crossing trees revisited: cutting down and spanning subtrees. Discrete Random Walks, DRW'03, 2003, Paris, France. pp.265-276, ⟨10.46298/dmtcs.3327⟩. ⟨hal-01183922⟩

Collections

TDS-MACS
39 Consultations
632 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More