Loading [MathJax]/jax/output/HTML-CSS/jax.js

Alois Panholzer - Non-crossing trees revisited: cutting down and spanning subtrees

dmtcs:3327 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03) - https://doi.org/10.46298/dmtcs.3327
Non-crossing trees revisited: cutting down and spanning subtreesConference paper

Authors: Alois Panholzer 1

  • 1 Institut für Algebra und Computermathematik

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.


Volume: DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)
Section: Proceedings
Published on: January 1, 2003
Imported on: May 10, 2017
Keywords: Non-crossing trees,generating function,limiting distributions,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]

7 Documents citing this article

Consultation statistics

This page has been seen 374 times.
This article's PDF has been downloaded 318 times.