Maximally probable tree topologies with $r$-furcation

Abstract

For a specific rooted labeled tree topology, a labeled history is a sequence of branchings that give rise to that labeled topology as it unfolds over time. Here, for $r$-furcating trees, we use a connection with Huffman trees from information theory to identify maximally probable rooted trees -- unlabeled $r$-furcating topologies whose labelings each have a number of labeled histories greater than or equal to those of all other labeled topologies. Our characterization of the unique maximally probable $r$-furcating unlabeled topology generalizes the Harding--Hammersley--Grimmett result identifying the maximally probable bifurcating unlabeled topology, and it provides a new proof for that result. We present a conjecture for the maximally probable $r$-furcating unlabeled topology if labeled histories are tabulated allowing for simultaneous branching events across multiple internal nodes of a tree.