Labeled histories and maximally probable labeled topologies with multifurcation
Emily H. Dickey & Noah A. Rosenberg · 2025
Read Labeled histories and maximally probable labeled topologies with multifurcation by Emily H. Dickey & Noah A. Rosenberg (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-16799.txt.
Introduction
Emily H. Dickey and Noah A. Rosenberg count labeled histories for evolutionary trees that allow multifurcation, where one ancestor can split into several lineages at once. A labeled history records the order in which labeled lineages coalesce, and the count depends on the tree's shape.
For trees whose internal nodes have between two and r offspring, the authors enumerate all labeled histories and the histories of any specific topology. They then show a shape result. The unlabeled topology whose labelings carry the most histories, the maximally probable shape, is the same with multifurcation allowed as in the strictly bifurcating case. A parallel treatment covers simultaneous branchings, with a conjecture for the optimal shape there. The combinatorics connect to precedence-constrained scheduling and to real processes where multifurcation occurs.
Catalog record
| CREATOR | Emily H. Dickey & Noah A. Rosenberg |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-16799
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Labeled histories and maximally probable labeled topologies with multifurcation Emily H. Dickey & Noah A. Rosenberg Abstract In mathematical phylogenetics, labeled histories describe the sequences by which sets of labeled lineages coalesce to a shared ancestral lineage. We study labeled histories for at-most- r r -furcating trees. Consider a rooted leaf-labeled tree in which internal nodes each have i i offspring, and i i is permitted to range from 2 to r r across internal nodes, for a specified value of r r . For labeled topologies with n n leaves, we enumerate the total number of labeled histories with at-most- r r -furcation. We enumerate the labeled histories possessed by a specific at-most- r r -furcating labeled topology. We then demonstrate that the maximally probable at-most- r r -furcating unlabeled topology on n ⩾ 2 n\geqslant 2 leaves—the unlabeled topology whose labelings have the largest number of labeled histories—is the maximally probable strictly bifurcating unlabeled topology on n n leaves. Finally, we enumerate labeled histories for at-most- r r -furcating labeled topologies in a setting that permits simultaneous branchings. We similarly reduce the problem of identifying the maximally probable at-most- r r -furcating unlabeled topology on n ⩾ 2 n\geqslant 2 leaves, allowing simultaneity, to that of identifying the maximally probable strictly bifurcating unlabeled topology on n n leaves, with simultaneity; we conjecture the shape of this bifurcating unlabeled topology. The computations contribute to the study of multifurcation, which arises in various biological processes, and they connect to analogous mathematical settings involving precedence-constrained scheduling. Keywords: labeled histories, multifurcation, phylogenetic models Mathematics subject classification (MSC2020): 05A15, 05C05, 92D15 Author for correspondence: Noah A. Rosenberg. Email: [email protected]. 1 Introduction In evolutionary models that give rise to tree structures, the labeled history is an important concept. For a leaf-labeled tree on n leaves, a labeled history encodes the sequence of branchings that produce the specific labeled tree topology. The labeled histories produce a state space for probabilistic computations; the enumerations of labeled histories with n leaves, and of labeled histories compatible with a specific n -leaf labeled topology, therefore assist in such computations. Under the Yule–Harding probability model on labeled histories [ 6 , 15 ] , each labeled history is equally likely to be produced by the process of evolutionary descent. Hammersley & Grimmett [ 5 ] , building on a conjecture of Harding [ 6 ] , described a sequence of bifurcating unlabeled tree shapes, growing with the number of leaves n , whose associated labeled topologies maximize the number of labeled histories among all labeled topologies at fixed numbers of leaves. Degnan & Rosenberg [ 1 ] termed these unlabeled shapes, and their associated labeled topologies, maximally probable : among labeled topologies with a fixed number of leaves, the labeled topologies with the maximally probable unlabeled shape have the highest probability under the Yule–Harding model. Degnan & Rosenberg [ 1 ] used the maximally probable unlabeled tree shapes in a proof concerning gene tree and species tree labeled topologies. The maximally probable shapes have also appeared in various other phylogenetic combinatorics problems [ 2 , 3 ] . Much of the mathematical study of evolutionary trees has focused on bifurcating trees. However, multifurcating trees—in which internal nodes of a tree might possess more than two immediate offspring—arise in the context of models for phenomena such as epidemic transmission, large family sizes, high variance in reproductive success, and adaptive radiation [ 4 , 8 , 11 ] . Mathematically convenient formulations for multifurcating trees include strict r -furcation , in which each internal node of a tree possesses precisely r immediate descendants for a constant r\geqslant 2 , and at-most- r -furcation , in which internal nodes are permitted to vary from 2 to r in their numbers of immediate descendants [ 8 ] . Previously, we extended classical enumeration results for labeled histories from bifurcating trees to strict r -furcation [ 2 ] . Specifically, (1) we enumerated the total number of labeled histories across all r -furcating labeled topologies with n leaves, and (2) we enumerated labeled histories for a specific labeled topology with n leaves. In addition, (3) we conjectured the maximally probable r -furcating unlabeled tree shape for n leaves. We also considered problems (1) and (2) in the setting in which simultaneous branching events are permitted, counting “tie-permitting labeled histories” both with bifurcation and with strict r -furcation. In this paper, we extend these results to at-most- r -furcation. For non-simultaneous at-most- r -furcation, we (1) we enumerate the total number of labeled histories across all at-most- r -furcating labeled topologies with n leaves, and (2) we enumerate labeled histories for a specific at-most- r -furcating labeled topology with n leaves. Next, (3) we show that the maximally probable at-most- r -furcating unlabeled tree shape on n leaves is the maximally probable bifurcating unlabeled tree shape on n leaves. For simultaneous at-most- r -furcation, we solve problems (1) and (2), enumerating the total number of tie-permitting labeled histories across all at-most- r -furcating labeled topologies and enumerating tie-permitting labeled histories for a specific at-most- r -furcating labeled topology on n leaves. We (3) reduce the problem of identifying the maximally probable at-most- r -furcating unlabeled tree shape on n leaves, with simultaneity, to that of identifying the maximally probable bifurcating unlabeled tree shape on n leaves, with simultaneity. We present a conjecture describing this bifurcating shape. 2 Definitions Definitions largely follow Dickey & Rosenberg [ 2 ] , tracing to Steel [ 13 ] and King & Rosenberg [ 7 ] ; definitions for at-most- r -furcating trees follow Maranca & Rosenberg [ 8 ] . We consider leaf-labeled, rooted trees T . Each leaf has a distinct label. For a tree T , nodes are leaf nodes or internal nodes ; the unique root node is included among internal nodes. The labeled topology of T is its topological structure together with its leaf labels. The unlabeled tree shape or unlabeled topology of T is the topological structure without the leaf labels. We indicate the number of leaves of T by |T| . For nodes v and u of T , u is descended from v and v is ancestral to u if v lies on the path from the root to u . A node is ancestral to itself and descended from itself. A pendant edge is an edge that connects an internal node to a leaf. A cherry node is an internal node with exactly two child nodes, both of which are leaves. For r\geqslant 2 , in an r -furcating tree , also termed a strictly r -furcating tree , each internal node has exactly r immediate descendant nodes. The generalization of a cherry node for r -furcating trees is a broomstick node , an internal node whose r children are all leaves. In an at-most- r -furcating tree , the number of immediate descendant nodes of an internal node ranges from 2 to r across internal nodes. Bifurcation corresponds to r=2 . Strictly r -furcating trees are also at-most- r -furcating. For an at-most- r -furcating tree T whose root has immediate subtrees T_{1},T_{2},\ldots,T_{k} , 2\leqslant k\leqslant r , we write