Further results on the inducibility of $d$-ary trees

Audace A. V. Dossou-Olory, Stephan Wagner

Published 2018-11-27Version 1

For a $d$-ary tree (every vertex has outdegree between $2$ and $d$) $D$ with $|D|=k$ leaves, let $\gamma(D,T)$ be the density of all subsets of $k$ leaves of the $d$-ary tree $T$ that induce a copy of $D$. The inducibility of $D$ is $\limsup_{|T|\to \infty}\gamma(D,T)$. We give a general upper bound on the inducibility of $D$ as a function of the inducibilities of its branches. Moreover, we demonstrate that the bound is sharp for infinitely many $d$-ary trees. A $d$-ary tree is called balanced if the number of leaves in any two of its branches differs at most by one. We obtain an improved upper bound on the inducibility of an arbitrary balanced $d$-ary tree. We give several examples proving that the bound is sharp for every given number of leaves. In particular, the precise inducibilities of certain balanced $d$-ary trees are derived. Furthermore, we present a lower bound that asymptotically matches the (improved) upper bound under specific restrictions. We also demonstrate that the sequence of complete $d$-ary trees contains a positive density of any fixed $d$-ary tree in the limit.