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

caterpillarcomplete binary treecrossing numberinducibilitysubtreestanglegram

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• 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

(12)

• Analogies between the crossing number and the tangle crossing number
• The minimum asymptotic density of binary caterpillars
• An infinite antichain of planar tanglegrams
• Inducibility of \(d\)-ary trees
• The shape of random tanglegrams
• Further results on the inducibility of d-ary trees
• Inducibility and universality for trees
• Trees of tangles in infinite separation systems
• On trees, tanglegrams, and tangled chains
• On the inducibility of small trees
• Inducibility of topological trees
• Getting to the root of the problem: sums of squares for limits of 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)