Inducibility in binary trees and crossings in random tanglegrams

الأصل · EN

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 γ(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 |ₜ| → ∞ γ(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.