The shape of random tanglegrams

DOI10.1016/J.AAM.2016.04.001zbMATH Open1385.60016arXiv1512.01168OpenAlexW2182049487MaRDI QIDQ281899FDOQ281899

Authors: Matjaž Konvalinka, Stephan Wagner 

Publication date: 11 May 2016

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

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.

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

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

zbMATH Keywords

automorphismsheightrandom plane binary treestanglegram

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Analytic combinatorics
• Random Trees
• The average height of binary trees and other simple trees
• Drawing (complete) binary tanglegrams
• Isomorphism and symmetries in random phylogenetic trees
• On the enumeration of tanglegrams and tangled chains
• The Distribution of Heights of Binary Trees and Other Simple Trees

Cited In (12)

• Title not available (Why is that?)
• On the enumeration of tanglegrams and tangled chains
• Characterizing planar tanglegram layouts and applications to edge insertion problems
• The correspondence induced on the pillowcase by the earring tangle
• Inducibility in binary trees and crossings in random tanglegrams
• An infinite antichain of planar tanglegrams
• Sampling planar tanglegrams and pairs of disjoint triangulations
• Tangles are Decided by Weighted Vertex Sets
• On trees, tanglegrams, and tangled chains
• Planar tanglegram layouts and single edge insertion
• Counting tanglegrams with species
• A tanglegram Kuratowski theorem

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)