DMTCS Proceedings, Discrete Random Walks, DRW'03

Font Size:  Small  Medium  Large

Non-crossing trees revisited: cutting down and spanning subtrees

Alois Panholzer


Here we consider two parameters for random non-crossing trees: (i) the number of random cuts to destroy a size-n non-crossing tree and (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 (ii) as a functional of a conditioned random walk, and although we do not have such an interpretation for parameter (i), we obtain here limiting distributions, that are also arising as limits of some functionals of conditioned random walks.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional