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 partitionsbinary treesenumerationtanglegrams

Mathematics Subject Classification ID

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

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

• Baxter permutations
• Cayley compositions, partitions, polytopes, and geometric bijections
• Drawing (complete) binary tanglegrams
• 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?)
• 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

(17)

• Chains in lattices of mappings and finite fuzzy topological spaces
• Analogies between the crossing number and the tangle crossing number
• Ricci-Ollivier curvature of the rooted phylogenetic subtree-prune-regraft graph
• Counting tanglegrams with species
• An infinite antichain of planar tanglegrams
• The shape of random tanglegrams
• On symmetries in phylogenetic trees
• scientific article; zbMATH DE number 7359764 (Why is no real title available?)
• On trees, tanglegrams, and tangled chains
• Enumeration and asymptotic formulas for rectangular partitions of the hypercube
• Inducibility in binary trees and crossings in random tanglegrams
• Planar tanglegram layouts and single edge insertion
• Sampling planar tanglegrams and pairs of disjoint triangulations
• Characterizing planar tanglegram layouts and applications to edge insertion problems
• The flip graph on planar layouts of a planar tanglegram is almost a hypercube
• Reconstruction of caterpillar tanglegrams
• Subdivergence-free gluings of trees

Describes a project that uses

Uses Software

• Tanglegrams
• OEIS
• SPRSupertrees

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)