Inducibility in binary trees and crossings in random tanglegrams

DOI10.1137/16M1060741MaRDI QIDQ5348495zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(11)

• Inducibility of topological trees
• 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

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)