More Like this

1. Enumeration of Rooted Binary Unlabeled Galled Trees

   https://doi.org/10.1007/s11538-024-01270-8  

   Agranat-Tamir, Lily; Mathur, Shaili; Rosenberg, Noah A. (March 2024, Bulletin of Mathematical Biology)

   Abstract Rooted binarygalledtrees generalize rooted binary trees to allow a restricted class of cycles, known asgalls. We build upon the Wedderburn-Etherington enumeration of rooted binary unlabeled trees withnleaves to enumerate rooted binary unlabeled galled trees withnleaves, also enumerating rooted binary unlabeled galled trees withnleaves andggalls,$$0 \leqslant g \leqslant \lfloor \frac{n-1}{2} \rfloor $$ $0⩽g⩽\lfloor \frac{n-1}{2}\rfloor$. The enumerations rely on a recursive decomposition that considers subtrees descended from the nodes of a gall, adopting a restriction on galls that amounts to considering only the rooted binarynormalunlabeled galled trees in our enumeration. We write an implicit expression for the generating function encoding the numbers of trees for alln. We show that the number of rooted binary unlabeled galled trees grows with$$0.0779(4.8230^n)n^{-\frac{3}{2}}$$ $0.0779(4.{8230}^n)n^{-\frac{3}{2}}$, exceeding the growth$$0.3188(2.4833^n)n^{-\frac{3}{2}}$$ $0.3188(2.{4833}^n)n^{-\frac{3}{2}}$of the number of rooted binary unlabeled trees without galls. However, the growth of the number of galled trees with only one gall has the same exponential order 2.4833 as the number with no galls, exceeding it only in the subexponential term,$$0.3910n^{\frac{1}{2}}$$ $0.3910n^{\frac{1}{2}}$compared to$$0.3188n^{-\frac{3}{2}}$$ $0.3188n^{-\frac{3}{2}}$. For a fixed number of leavesn, the number of gallsgthat produces the largest number of rooted binary unlabeled galled trees lies intermediate between the minimum of$$g=0$$ $g=0$and the maximum of$$g=\lfloor \frac{n-1}{2} \rfloor $$ $g=\lfloor \frac{n-1}{2}\rfloor$. We discuss implications in mathematical phylogenetics. 

   more » « less
2. Bijections between the multifurcating unlabeled rooted trees and the positive integers

   https://doi.org/10.1016/j.aam.2023.102612  

   Maranca, Alessandra_Rister Portinari; Rosenberg, Noah A (February 2024, Advances in Applied Mathematics)

   Colijn and Plazzotta (2018) [1] described a bijective scheme for associating the unlabeled bifurcating rooted trees with the positive integers. In mathematical and biological applications of unlabeled rooted trees, however, nodes of rooted trees are sometimes multifurcating rather than bifurcating. Building on the bijection between the unlabeled bifurcating rooted trees and the positive integers, we describe bijective schemes for associating the unlabeled multifurcating rooted trees with the positive integers. We devise bijections with the positive integers for a set of trees in which each non-leaf node has exactly k child nodes, and for a set of trees in which each non-leaf node has at most k child nodes. The calculations make use of Macaulay's binomial expansion formula. The generalization to multifurcating trees can assist with the use of unlabeled trees for applications in evolutionary biology, such as the measurement of phylogenetic patterns of genetic lineages in pathogens. 

   more » « less
3. Dispersed graph labellings

   Martin, William J; Stinson, Douglas R (February 2024, Australasian Journal of Combinatorics)

   Albert, Michael; Billington, Elizabeth J (Ed.)

   A k-dispersed labelling of a graph G on n vertices is a labelling of the vertices of G by the integers 1,...,n such that d(i,i+1) ≥ k for 1 ≤ i ≤ n − 1. Here DL(G) denotes the maximum value of k such that G has a k-dispersed labelling. In this paper, we study upper and lower bounds on DL(G). Computing DL(G) is NP-hard. However, we determine the exact value of DL(G) for cycles, paths, grids, hypercubes and complete binary trees. We also give a product construction and we prove a degree-based bound. 

   more » « less
4. All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees

   https://doi.org/10.1186/s13015-023-00224-4  

   Mathur, Shaili; Rosenberg, Noah A. (December 2023, Algorithms for Molecular Biology)

   Abstract Objective In mathematical phylogenetics, a labeled rooted binary tree topology can possess any of a number of labeled histories, each of which represents a possible temporal ordering of its coalescences. Labeled histories appear frequently in calculations that describe the combinatorics of phylogenetic trees. Here, we generalize the concept of labeled histories from rooted phylogenetic trees to rooted phylogenetic networks, specifically for the class of rooted phylogenetic networks known as rooted galled trees . Results Extending a recursive algorithm for enumerating the labeled histories of a labeled tree topology, we present a method to enumerate the labeled histories associated with a labeled rooted galled tree. The method relies on a recursive decomposition by which each gall in a galled tree possesses three or more descendant subtrees. We exhaustively provide the numbers of labeled histories for all small galled trees, finding that each gall reduces the number of labeled histories relative to a specified galled tree that does not contain it. Conclusion The results expand the set of structures for which labeled histories can be enumerated, extending a well-known calculation for phylogenetic trees to a class of phylogenetic networks. 

   more » « less
5. Projections of the Aldous chain on binary trees: Intertwining and consistency

   https://doi.org/10.1002/rsa.20930  

   Forman, Noah; Pal, Soumik; Rizzolo, Douglas; Winkel, Matthias (May 2020, Random Structures & Algorithms)

   Consider the Aldous Markov chain on the space of rooted binary trees withnlabeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix 1 ≤ k<nand project the leaf mass onto the subtree spanned by the firstkleaves. This yields a binary tree with edge weights that we call a “decoratedk‐tree with total massn.” We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decoratedk‐trees evolve as Markov chains themselves, and are projectively consistent overk. The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is then→∞continuum analog of the Aldous chain and will be taken up elsewhere. 

   more » « less