On the distribution of subtree orders of a tree
Date
2018
Journal Title
Journal ISSN
Volume Title
Publisher
University of Primorska
Abstract
We investigate the distribution of the number of vertices of a randomly chosen subtree of a tree. Specifically, it is proven that this distribution is close to a Gaussian distribution in an explicitly quantifiable way if the tree has sufficiently many leaves and no long branchless paths. We also show that the conditions are satisfied asymptotically almost surely for random trees. If the conditions are violated, however, we exhibit by means of explicit counterexamples that many other (non-Gaussian) distributions can occur in the limit. These examples also show that our conditions are essentially best possible.
Description
CITATION: Ralaivaosaona, D. & Wagner, S. 2018. On the distribution of subtree orders of a tree. Ars Mathematica Contemporanea, 14(1):129-156, doi:10.26493/1855-3974.996.675.
The original publication is available at https://amc-journal.eu
The original publication is available at https://amc-journal.eu
Keywords
Trees (Graph theory), Normal distribution, Homeomorphically irreducible trees, Random variables, Gaussian distribution, Free probalility theory, Asymptotic distribution (Probability theory)
Citation
Ralaivaosaona, D. & Wagner, S. 2018. On the distribution of subtree orders of a tree. Ars Mathematica Contemporanea, 14(1):129-156, doi:10.26493/1855-3974.996.675.