2024/06/05 by Louigi Addario‐Berry, Marie Albenque, Addario-Berry, Louigi +5 · 1 citation
Mathematics · Computer Science · #Stochastic processes and statistical mechanics #Bayesian Methods and Mixture Models #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2406.03025
The Horton-Strahler number of a rooted tree T is the height of the tallest complete binary tree that can be homeomorphically embedded in T. The number of full binary trees with n internal vertices and Horton-Strahler number s is known to be the same as the number of Dyck paths of length 2n whose height h satisfies \lfloor log2(1+h)\rfloor=s. In this paper, we present a new bijective proof of the above result, that in fact strengthens and refines it as follows. We introduce a sequence of trees (τi,i ≥ 0) which "interpolates" the complete binary trees, in the sense that τ2h-1 is the complete binary tree of height h for all h ≥ 0, and τi+1 strictly contains τi for all i ≥ 0. Defining S(T) to be the largest i for which τi can be homeomorphically embedded in T, we then show that the number of full binary trees T with n internal vertices and with S(T)=h is the same as the number of Dyck paths of length 2n with height h. (We call S(T) the refined Horton-Strahler number of T.) Our proof is bijective and relies on a recursive decomposition of binary trees (resp. Dyck paths) into subtrees with strictly smaller refined Horton-Strahler number (resp. subpaths with strictly smaller height). In a subsequent paper, we will show that the bijection has a continuum analogue, which transforms a Brownian continuum random tree into a Brownian excursion and under which (a continuous analogue of) the refined Horton-Strahler number of the tree becomes the height of the excursion.