3
$\begingroup$

Given a rooted tree $T_r$ (up to isomorphism), define the probability $P(T_r)$ as the probability of ending up with $T_r$ if one starts with a single (root) vertex and incrementally connects new vertices one-by-one, such that at each step the vertex being connected to on the existing tree is chosen at random

For example: There are 4 4-vertex rooted trees (up to isomorphism). 3 have probability: $1/6$, and 1 has probability: $1/2$

$v$--$v_r$--$v$--$v$

I came up with a Java program for calculating these probabilities, but this is only feasible for trees of up to about 12 or 13 vertices.

The question is: Is there any formula or algorithm for calculating the probability of a tree, based on the attributes of 2 or more of its subtrees?

$\endgroup$
1
  • $\begingroup$ Given how many trees there are, I would expect direct calculation to be feasible up to the low 20s (unless the problem is that the exact values of the probabilities start to take up too much memory). $\endgroup$ Dec 2, 2021 at 17:39

1 Answer 1

2
$\begingroup$

We can see any tree $T$ as the Hasse diagram of a poset whose smallest element is the root. I will freely identify the tree with the corresponding poset.

If we label by $i$ the $i$'th vertex added in the process, we get a rooted tree equipped with a linear extension, and each such equipped rooted tree occur with probability $\frac{1}{(n-1)!}$ (where $n$ is the number of vertices). The number of ways to get a given rooted tree in this way is the number of linear extensions of this tree up to automorphisms of the rooted tree.

Hence the probability you're looking for is given by $$\frac{L(T)}{|\text{Aut}(T)| (n-1)!}$$ where $L(T)$ is the number of linear extensions of $T$ and $\text{Aut}(T)$ is the automorphism group of $T$. There are algorithms for computing the former in $O(n^2)$ (https://www.researchgate.net/publication/226291352_On_computing_the_number_of_linear_extensions_of_a_tree). I am not sure for the latter, but it can probably be computed efficiently using a variant of the AHU algorithm.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.