0
$\begingroup$

My question is about a sentence in the proof of the following proposition:


Proposition 2.3. The uniform random tree $\mathbb{T}_{n}$ has the same distribution as a tree generated as follows:

  • Take a Galton-Watson tree with Poisson(1) offspring distribution;
  • Condition it to have total progeny precisely (n);
  • Assign the vertices random labels chosen from [n] and forget the original ordering.

Proof. Recall the standard labelling of the vertices of a Galton-Watson tree $\mathbf{T}$, and let $\mathbf{t}$ be a particular tree with $\#(\mathbf{t})=n$ and numbers of offspring $c\left(v_{1}\right)=c_{1}, \ldots, c\left(v_{n}\right)=c_{n}$. Then $$ \mathbb{P}(\mathbf{T}=\mathbf{t})=\prod_{i=1}^{n} \frac{e^{-1}}{c_{i} !}=e^{-n} \prod_{i=1}^{n} \frac{1}{c_{i} !} $$ Now observe that $\mathbb{P}(\#(\mathbf{T})=n)$ is a function only of $n$. Hence, $$ \mathbb{P}(\mathbf{T}=\mathbf{t} \mid \#(\mathbf{T})=n)=f(n) \prod_{i=1}^{n} \frac{1}{c_{i} !} $$ for some function $f$. Now consider labelling the vertices of $\mathbf{T}$ with $[n]:=\{1,2, \ldots, n\}$. There are $n!$ different ways to do this, of which $\prod_{i=1}^{n} c_{i} !$ give rise to the same unordered labelled tree, once we forget the ordering. Hence, the probability of obtaining a particular labelled unordered tree $t$ is $f(n) / n !$. Since this depends only on $n$, and not on any other feature of the tree, it must be the case that the tree is uniformly distributed on $\mathbb{T}_{n}$.

(From An introduction to random trees by Christina Goldschmidt )


There is one part I do not understand, why do $\prod_{i=1}^{n} c_{i} !$ out of the $n!$ different ways give rise to the same unordered labelled tree?

$\endgroup$

1 Answer 1

1
$\begingroup$

Permuting the offspring of any subset of the vertices does not change the unlabelled tree, because it preserves all of the parent-child relationships that define the tree. For each $k\in[n]$ there are $c_k!$ ways to permute the offspring of $v_k$, so there are altogether $\prod_{k=1}^nc_k!$ ways to permute the offspring of each vertex: you can combine any of the $c_1!$ permutations of the offspring of $v_1$ with any of the $c_2!$ permutations of the offspring of $v_2$ and so on without changing the underlying unlabelled tree.

Or you can turn it around. Suppose that $T$ is an unlabelled (rooted) tree on $n$ vertices. In the standard labelling the root must be labelled $\varnothing$. If it has $c_1$ offspring, they can then be labelled $1,2,\ldots,c_1$ in any of $c_1!$ orders. If the vertex now labelled $1$ has $c_2$ offspring, these can be labelled $11,12,\ldots,1c_2$ in any of $c_2!$ different orders. Continuing in this fashion, it the numbers of offspring of the $n$ vertices are $c_1,\ldots,c_k$, we have $\prod_{k=1}^nc_k!$ different ways to label the vertices using the standard labelling, depending on how we order the offspring of each vertex.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .