2018/11/27 by Audace A. V. Dossou-Olory, Stephan Wagner, Dossou-Olory, Audace A. V. +1
Mathematics · #05C05 #05C35 #05C60 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1811.11235
openalex publication_date 2018/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A subset of leaves of a rooted tree induces a new tree in a natural way. The density of a tree D inside a larger tree T is the proportion of such leaf-induced subtrees in T that are isomorphic to D among all those with the same number of leaves as D. The inducibility of D measures how large this density can be as the size of T tends to infinity. In this paper, we explicitly determine the inducibility in some previously unknown cases and find general upper and lower bounds, in particular in the case where D is balanced, i.e., when its branches have at least almost the same size. Moreover, we prove a result on the speed of convergence of the maximum density of D in strictly d-ary trees T (trees where every internal vertex has precisely d children) of a given size n to the inducibility as n → ∞, which supports an open conjecture.