The minimum asymptotic density of binary caterpillars

Abstract

Given $d\ge 2$ and two rooted $d$-ary trees $D$ and $T$ such that $D$ has $k$ leaves, the density $\gamma (D,T)$ of $D$ in $T$ is the proportion of all $k$-element subsets of leaves of $T$ that induce a tree isomorphic to $D$, after erasing all vertices of outdegree $1$. In a recent work, it was proved that the limit inferior of this density as the size of $T$ grows to infinity is always zero unless $D$ is the $k$-leaf binary caterpillar $F_k^2$ (the binary tree with the property that a path remains upon removal of all the $k$ leaves). Our main theorem in this paper is an exact formula (involving both $d$ and $k$) for the limit inferior of $\gamma (F_k^2,T)$ as the size of $T$ tends to infinity.

arXiv comment16 pages