Consider two random tree models $T_1(n)$ and $T_2(n)$, chosen equiprobably among labelled and unlabelled trees on $n$ vertices respectively. I'm wondering if there are properties that are vastly more present in one model than another. That is, what are examples of natural property functions $f$ such that $\Pr(f(T_1(n)))/\Pr(f(T_2(n))) \to 0$ or $\infty$ significantly fast as $n \to \infty$? Can one of the probabilities tend to $0$, and the other tend to $1$?

  • $\begingroup$ Is $f$ defined on both labeled and unlabeled trees? Or do you mean that labeling of the former is ignored before applying $f$? $\endgroup$ – Max Alekseyev Nov 6 '18 at 12:50
  • $\begingroup$ $f$ should not discern between isomorphic trees. $\endgroup$ – Mikhail Tikhomirov Nov 6 '18 at 14:32
  • $\begingroup$ Check out Ralph Freese's paper "On the two kinds of probability in algebra". He addresses (a version of) this question for general algebraic structures and answers it essentially in the negative. You may find the arguments applicable to your situation, or at least learn some f to avoid. Gerhard "Things Good To Know About " Paseman, 2018.11.06. $\endgroup$ – Gerhard Paseman Nov 6 '18 at 15:46

Surely, these should be properties which w.h.p. imply that there are many (or few) automorphisms of an (unlabelled) tree. Not sure whether this counts, but here are few candidates of some random variables which seem to correlate with the number of automorphisms.

The most obvious one is, surely, the number of automorphisms itself;). So, a labelled tree should (at average) have more automorphisms (as an unlabelled tree) than an unlabelle one.

Another example is the number of leaves: if a tree has many leaves, it is likely that some of them are attached to one vertex, and so permutations of them provide automorphisms of the tree. And, indeed, the probability that a certain vertex of a labelled tree is a leaf is $(1-1/n)^{n-2}$ (since the vertex is a leaf iff it does not appear in the Pruefer code), so the average number of leaves in it is around $n/e$. The situation with unlabelled trees is harder, but it should be close to the situation with the rooted unlabelled trees. For such, the probability that the root is a leaf is the ratio of the number of rooted trees on $n-1$ vertex to that on $n$ vertices, and it tends to $1/\alpha$ where $\alpha=2.955765,,,$. Hence, the average number of leaves in an unlabelled tree should be not far from $n/\alpha$.

So, it seems that one valid property is, say, `the tree has at least $7n/20$ leaves'; I do not know, however, whether it counts as natural...


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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