The shape of random tanglegrams

DOI10.1016/J.AAM.2016.04.001MaRDI QIDQ281899zbMATH OpenOpenAlexFDO

Authors Matjaž Konvalinka, Stephan Wagner

Publication date 11 May 2016

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

automorphismsheightrandom plane binary treestanglegram

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Abstract: A tanglegram consists of two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the trees. We show that the two halves of a random tanglegram essentially look like two independently chosen random plane binary trees. This fact is used to derive a number of results on the shape of random tanglegrams, including theorems on the number of cherries and generally occurrences of subtrees, the root branches, the number of automorphisms, and the height. For each of these, we obtain limiting probabilities or distributions. Finally, we investigate the number of matched cherries, for which the limiting distribution is identified as well.

Recommendations

• On the enumeration of tanglegrams and tangled chains
• On trees, tanglegrams, and tangled chains
• scientific article; zbMATH DE number 7359764
• Inducibility in binary trees and crossings in random tanglegrams
• Counting tanglegrams with species

Cites work

• Analytic combinatorics
• Drawing (complete) binary tanglegrams
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Isomorphism and symmetries in random phylogenetic trees
• On the enumeration of tanglegrams and tangled chains
• Random Trees
• The average height of binary trees and other simple trees
• The Distribution of Heights of Binary Trees and Other Simple Trees

Cited in

(14)

• Counting tanglegrams with species
• An infinite antichain of planar tanglegrams
• On the enumeration of tanglegrams and tangled chains
• scientific article; zbMATH DE number 7359764 (Why is no real title available?)
• A tanglegram Kuratowski theorem
• On trees, tanglegrams, and tangled chains
• Tangles are Decided by Weighted Vertex Sets
• Inducibility in binary trees and crossings in random tanglegrams
• The correspondence induced on the pillowcase by the earring tangle
• 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

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: The shape of random tanglegrams

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