The minimum asymptotic density of binary caterpillars

Abstract: Given

d g e q 2

and two rooted

d

-ary trees

D

and

T

such that

D

has

k

leaves, the density

g a m m a (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

g a m m a (F_{k}^{2}, T)

as the size of

T

tends to infinity.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: The minimum asymptotic density of binary caterpillars