2024/09/27 by Luc Devroye, Devroye, Luc, Michael R. Doboli +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2409.18956
openalex publication_date 2024/09/27 · openalex created_date 2024/10/27 · openalex updated_date 2026/08/01
The Colijn--Plazzotta ranking is a bijective encoding of the unlabeled binary rooted trees with positive integers. We show that the rank f(t) of a tree t is closely related to its height h, the length of the longest path from a leaf to the root. We consider the rank f(τn) of a random n-leaf tree τn under each of three models: (i) uniformly random unlabeled unordered binary rooted trees, or unlabeled topologies; (ii) uniformly random leaf-labeled binary trees, or labeled topologies under the uniform model; and (iii) random binary search trees, or labeled topologies under the Yule--Harding model. Relying on the close relationship between tree rank and tree height, we obtain results concerning the asymptotic properties of log log f(τn). In particular, we find 𝔼 \log2 log f(τn)\ ∼ 2 √(πn) for uniformly random unlabeled ordered binary rooted trees and uniformly random leaf-labeled binary trees, and for a constant α≈ 4.31107, 𝔼\log2 log f(τn)\ ∼ αlog n for leaf-labeled binary trees under the Yule--Harding model. We show that the mean of f(τn) itself under the three models is largely determined by the rank cn-1 of the highest-ranked tree -- the caterpillar -- obtaining an asymptotic relationship with πn cn-1, where πn is a model-specific function of n. The results resolve open problems, providing a new class of results on an encoding useful in mathematical phylogenetics.