On the enumeration of tanglegrams and tangled chains

DOI10.1016/J.JCTA.2016.10.003MaRDI QIDQ346449zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

binary treesenumerationtanglegramsbinary partitions

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 5995471 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 3232846 (Why is no real title available?)
• Baxter permutations
• Cayley compositions, partitions, polytopes, and geometric bijections
• Drawing (complete) binary tanglegrams
• Matchings and phylogenetic trees
• On non-squashing partitions
• On symmetries in phylogenetic trees
• Shuffle of parenthesis systems and Baxter permutations
• Stack words, standard tableaux and Baxter permutations
• Subtree transfer operations and their induced metrics on evolutionary trees
• The generation of random, binary unordered trees
• The number of Baxter permutations
• The shape of random tanglegrams

Cited in

(14)

• Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph
• scientific article; zbMATH DE number 7359764 (Why is no real title available?)
• 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

Describes a project that uses

Uses Software

• Tanglegrams
• SPRSupertrees
• OEIS

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)