pith. sign in

arxiv: 1804.05731 · v1 · pith:OCWHXRIKnew · submitted 2018-04-16 · 🧮 math.CO

The minimum asymptotic density of binary caterpillars

classification 🧮 math.CO
keywords binarydensityleavesgammainferiorinfinitylimitsize
0
0 comments X
read the original abstract

Given $d\geq 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^2_k$ (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^2_k,T)$ as the size of $T$ tends to infinity.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.