Sara Billey ; Matjaz Konvalinka ; Frderick Matsen IV - On trees, tanglegrams, and tangled chains

dmtcs:6348 - Discrete Mathematics & Theoretical Computer Science, April 22, 2020, DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016) - https://doi.org/10.46298/dmtcs.6348
On trees, tanglegrams, and tangled chainsArticle

Authors: Sara Billey 1; Matjaz Konvalinka 2; Frderick Matsen IV

  • 1 Department of Mathematics [Seattle]
  • 2 Departement of Mathematics [Slovenia]

Tanglegrams are a class of graphs arising in computer science and in biological research on cospeciation and coevolution. They are formed by identifying the leaves of two rooted binary trees. The embedding of the trees in the plane is irrelevant for this application. We give an explicit formula to count the number of distinct binary rooted tanglegrams with n matched leaves, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This work gives a new formula for the number of binary trees with n leaves. Several open problems and conjectures are included along with pointers to several followup articles that have already appeared.


Volume: DMTCS Proceedings, 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016)
Published on: April 22, 2020
Imported on: July 4, 2016
Keywords: [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Combinatorial and Algebraic Aspects of Varieties; Funder: National Science Foundation; Code: 1101017
  • ATD Collaborative Research: New theorems and algorithms for comprehensive analysis of metagenomic data via statistical phylogenetics; Funder: National Science Foundation; Code: 1223057

Consultation statistics

This page has been seen 204 times.
This article's PDF has been downloaded 245 times.