Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01183922
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 12, 2015 - 9:06:36 AM
Last modification on : Thursday, May 11, 2017 - 1:02:54 AM
Long-term archiving on: : Friday, November 13, 2015 - 11:37:09 AM

File

dmAC0125.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01183922, version 1

Collections

Citation

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

Share

Metrics

Record views

73

Files downloads

539