Inducibility in binary trees and crossings in random tanglegrams

DOI10.1137/16M1060741zbMATH Open1368.05022arXiv1601.07149OpenAlexW2963429056MaRDI QIDQ5348495FDOQ5348495

Authors: Éva Czabarka, László A. Székely, Stephan Wagner 

Publication date: 18 August 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: In analogy to other concepts of a similar nature, we define the inducibility of a rooted binary tree. Given a fixed rooted binary tree $B$ with $k$ leaves, we let $gamma(B,T)$ be the proportion of all subsets of $k$ leaves in $T$ that induce a tree isomorphic to $B$. The inducibility of $B$ is $limsu{p}_{|T|oinfty}gamma(B,T)$. We determine the inducibility in some special cases, show that every binary tree has positive inducibility and prove that caterpillars are the only binary trees with inducibility $1$. We also formulate some open problems and conjectures on the inducibility. Finally, we present an application to crossing numbers of random tanglegrams.

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

Recommendations

• The shape of random tanglegrams
• Inducibility of topological trees
• On trees, tanglegrams, and tangled chains
• On the inducibility of small trees
• Inducibility of \(d\)-ary trees

zbMATH Keywords

tanglegramcrossing numbersubtreescomplete binary treecaterpillarinducibility

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Taxonomy, cladistics, statistics in mathematical biology (92B10) Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62) Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Title not available (Why is that?)
• Reconstructing the shape of a tree from observed dissimilarity data
• Tree structures for proximity data
• Kaikoura tree theorems: Computing the maximum agreement subtree
• The shape of random tanglegrams
• On the enumeration of tanglegrams and tangled chains
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
• The inducibility of graphs
• The inducibility of blow-up graphs
• On the local profiles of trees
• A note on the inducibility of 4-vertex graphs
• The maximum agreement subtree problem
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Bounds on the expected size of the maximum agreement subtree
• Turán's brick factory problem: the status of the conjectures of Zarankiewicz and Hill

Cited In (11)

• Trees of tangles in infinite separation systems
• The minimum asymptotic density of binary caterpillars
• Further results on the inducibility of \(d\)-ary trees
• The shape of random tanglegrams
• Analogies between the crossing number and the tangle crossing number
• An infinite antichain of planar tanglegrams
• Inducibility of \(d\)-ary trees
• On the inducibility of small trees
• On trees, tanglegrams, and tangled chains
• Inducibility and universality for trees
• Inducibility of topological trees

This page was built for publication: Inducibility in binary trees and crossings in random tanglegrams

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