Bernhard Gittenberger - The profile of unlabeled trees

dmtcs:3352 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms - https://doi.org/10.46298/dmtcs.3352
The profile of unlabeled treesConference paper

Authors: Bernhard Gittenberger 1

  • 1 Institut für Diskrete Mathematik und Geometrie [Wien]


We consider the number of nodes in the levels of unlabeled rooted random trees and show that the joint distribution of several level sizes (where the level number is scaled by $\sqrt{n}$) weakly converges to the distribution of the local time of a Brownian excursion evaluated at the times corresponding to the level numbers. This extends existing results for simply generated trees and forests to the case of unlabeled rooted trees.

https://doi.org/10.46298/dmtcs.3352
Source: HAL:hal-01184024v1
Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: [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], [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], [en] unlabeled trees, profile, Brownian excursion, local time
Funding:
    Source : OpenAIRE Graph
  • Automatic Expansion of Generating Functions; Code: P 16053

Share and export

Consultation statistics

This page has been seen 417 times.
This article's PDF has been downloaded 307 times.