# Typical labelled vs. unlabelled trees properties

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$$?

• Is $f$ defined on both labeled and unlabeled trees? Or do you mean that labeling of the former is ignored before applying $f$? – Max Alekseyev Nov 6 '18 at 12:50
• $f$ should not discern between isomorphic trees. – Mikhail Tikhomirov Nov 6 '18 at 14:32
• 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. – Gerhard Paseman Nov 6 '18 at 15:46

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...