On the enumeration of tanglegrams and tangled chains

DOI10.1016/J.JCTA.2016.10.003zbMATH Open1351.05116arXiv1507.04976OpenAlexW2962729470MaRDI QIDQ346449FDOQ346449

Authors: Sara Billey, Matjaž Konvalinka, Frederick A. IV Matsen 

Publication date: 29 November 2016

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Tanglegrams are a special class of graphs appearing in applications concerning cospeciation and coevolution in biology and computer science. They are formed by identifying the leaves of two rooted binary trees. We give an explicit formula to count the number of distinct binary rooted tanglegrams with $n$ matched vertices, 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 includes a new formula for the number of binary trees with $n$ leaves. We also give a conjecture for the expected number of cherries in a large randomly chosen binary tree and an extension of this conjecture to other types of trees.

Full work available at URL: https://arxiv.org/abs/1507.04976

Recommendations

• On trees, tanglegrams, and tangled chains
• scientific article; zbMATH DE number 7359764
• Counting tanglegrams with species
• The shape of random tanglegrams
• Analogies between the crossing number and the tangle crossing number

zbMATH Keywords

binary treesenumerationtanglegramsbinary partitions

Mathematics Subject Classification ID

Applications of graph theory (05C90) Trees (05C05) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Subtree transfer operations and their induced metrics on evolutionary trees
• Shuffle of parenthesis systems and Baxter permutations
• On non-squashing partitions
• Title not available (Why is that?)
• Drawing (complete) binary tanglegrams
• The shape of random tanglegrams
• On symmetries in phylogenetic trees
• The generation of random, binary unordered trees
• The number of Baxter permutations
• Stack words, standard tableaux and Baxter permutations
• Cayley compositions, partitions, polytopes, and geometric bijections
• Title not available (Why is that?)
• Matchings and phylogenetic trees
• Baxter permutations

Cited In (14)

• Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph
• Title not available (Why is that?)
• The shape of random tanglegrams
• Chains in lattices of mappings and finite fuzzy topological spaces
• Analogies between the crossing number and the tangle crossing number
• Characterizing planar tanglegram layouts and applications to edge insertion problems
• Inducibility in binary trees and crossings in random tanglegrams
• Enumeration and asymptotic formulas for rectangular partitions of the hypercube
• An infinite antichain of planar tanglegrams
• On symmetries in phylogenetic trees
• Sampling planar tanglegrams and pairs of disjoint triangulations
• On trees, tanglegrams, and tangled chains
• Planar tanglegram layouts and single edge insertion
• Counting tanglegrams with species

Uses Software

• OEIS
• SPRSupertrees
• Tanglegrams

This page was built for publication: On the enumeration of tanglegrams and tangled chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q346449)