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. 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
3. Testing Equality Under the Local Broadcast Model

   https://doi.org/https://doi.org/10.1007/978-3-030-79527-6_15  

   Khan M.S., Vaidya N.H. (June 2021, 28th International Colloquium on Structural Information and Communication Complexity)

   Jurdziński, T; Schmid, S (Ed.)

   In the multiparty equality problem, each of the n nodes starts with a k-bit input. If there is a mismatch between the inputs, then at least one node must be able to detect it. The cost of a multiparty equality protocol is the total number of bits sent in the protocol. We consider the problem of minimizing this communication cost under the local broadcast model for the case where the underlying communication graph is undirected. In the local broadcast model of communication, a message sent by a node is received identically by all of its neighbors. This is in contrast to the classical point-to-point communication model, where a message sent by a node to one of its neighbors is received only by its intended recipient. Under point-to-point communication, there exists a simple protocol which is competitive within a factor 2 of the lower bound [1]. In this protocol, a rooted spanning tree is fixed and each node sends its entire input to its parent in the tree. On receiving a value from its child, a node compares it against its own input to check if the two values match. Ignoring lower order additive terms, a more complicated protocol comes within a factor 4/3 of the lower bound and is tight for certain classes of graphs [1]. Tight results, ignoring lower order terms, are also known for complete graphs [2, 9]. We study the multiparty equality problem under the local broadcast model. Recently, our work has shown that the connectivity requirements for Byzantine consensus are lower in the local broadcast model as compared to the classical model [7, 8]. In this work, 1. we identify a lower bound for the multiparty equality problem in this model. 2. we first identify simple protocols, wherein nodes are restricted to either transmit their entire input or not transmit anything at all, and find that these can cost Ω(logn) times the lower bound using existing example for the set cover problem [12]. 3. we then design a protocol to solve the problem within a constant factor of the lower bound. 

   more » « less
4. Asymptotic Enumeration of Rooted Binary Unlabeled Galled Trees with a Fixed Number of Galls

   https://doi.org/10.4230/LIPIcs.AofA.2024.27  

   Agranat-Tamir, Lily; Fuchs, Michael; Gittenberger, Bernhard; Rosenberg, Noah A (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mailler, Cécile; Wild, Sebastian (Ed.)

   Galled trees appear in problems concerning admixture, horizontal gene transfer, hybridization, and recombination. Building on a recursive enumerative construction, we study the asymptotic behavior of the number of rooted binary unlabeled (normal) galled trees as the number of leaves n increases, maintaining a fixed number of galls g. We find that the exponential growth with n of the number of rooted binary unlabeled normal galled trees with g galls has the same value irrespective of the value of g ≥ 0. The subexponential growth, however, depends on g; it follows c_g n^{2g-3/2}, where c_g is a constant dependent on g. Although for each g, the exponential growth is approximately 2.4833ⁿ, summing across all g, the exponential growth is instead approximated by the much larger 4.8230ⁿ. 

   more » « less
5. Computing the Bounds of the Number of Reticulations in a Tree-Child Network That Displays a Set of Trees

   https://doi.org/10.1089/cmb.2023.0309  

   Wu, Yufeng; Zhang, Louxin (April 2024, Journal of Computational Biology)

   Phylogenetic network is an evolutionary model that uses a rooted directed acyclic graph (instead of a tree) to model an evolutionary history of species in which reticulate events (e.g., hybrid speciation or horizontal gene transfer) occurred. Tree-child network is a kind of phylogenetic network with structural constraints. Existing approaches for tree-child network reconstruction can be slow for large data. In this study, we present several computational approaches for bounding from below the number of reticulations in a tree-child network that displays a given set of rooted binary phylogenetic trees. In addition, we also present some theoretical results on bounding from above the number of reticulations. Through simulation, we demonstrate that the new lower bounds on the reticulation number for tree-child networks can practically be computed for large tree data. The bounds can provide estimates of reticulation for relatively large data. 

   more » « less