3
$\begingroup$

Consider the class of rooted trees and suppose I have at my disposal a lowest common ancestor (LCA) operator given by $$ \textrm{lca}(u,v) = \text{the lowest common ancestor of $u$ and $v$} $$ for all vertices $u,v$ belonging to the same tree.

Given $k$ vertices from a tree, I can apply my LCA operator to all pairs of vertices and thereby obtain new vertices to which I can apply the LCA operator once again etc. etc. In this way we construct a tree that contains the $k$ original vertices and has at most $2k-1$ vertices in total (easy to see).

Examples:

  • If the $k$ vertices are all leaves in a full, binary tree, then the constructed tree is the full, binary tree tree with $2k-1$ vertices.
  • If the $k$ vertices all belong to the same path, then the constructed tree is just a path of length $k$.

How many different trees can be constructed in this way from $k$ vertices using the LCA operator?

Said differently (in a labeled version which is OK): How many rooted trees are there with $k$ labeled vertices and all other vertices being generated from those $k$ vertices using an LCA operator?

An asymptotic formula or a good lower bound would be fine.

$\endgroup$
2
  • 1
    $\begingroup$ For asymptotics, an upper bound on the number of k generated semilattices may help you. For labeled elements, the number is something like doubly exponential ($2^{2^k}$). For lower bounds look at general tree enumeration and consider trees wth k leaves and k+n vertices for n much smaller than k. Gerhard "Ask Me About System Design" Paseman, 2013.05.24 $\endgroup$ May 25, 2013 at 6:40
  • 1
    $\begingroup$ An upper bound with a double exponential looks very big to me. After all, there are at most $(2k-1)^{2k-3}$ labeled trees with $2k-1$ nodes. I have already looked at some enumeration results, but none of them give me exactly what I am looking for. I have now added another way of stating my question. $\endgroup$
    – Esben
    May 25, 2013 at 8:42

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.