pr.probability - Is there a simple inductive procedure for generating labeled trees uniformly at random, without direct recourse to Prüfer sequences?

This is an interesting question. For any fixed positive integer $d geq 2$, write $T_d^{infty}$
for the complete infinite rooted $d$-ary tree (by this I mean every node has exactly $d$ children). Luczak and Winkler proved the existence of a procedure which will generate a sequence $(T_{n,d})_{n geq 0}$ such that for all $n geq 1$,

(a) the distribution of T_{n,d} is uniformly random over all $n$-node subtrees of $T^{infty}_d$ that contain the root of $T^{infty}_d$; and

(b) $T_{n,d}$ is a subtree of $T_{n+1,d}$.

It is not hard to show that (a) implies that for all $n$, $T_{n,d}$ is distributed as a Galton-Watson tree with offspring distribution $mathrm{Bin}(d,1/d)$, conditioned to have total size $n$.
Since $mathrm{Bin}(d,1/d)$ tends to a $mathrm{Poisson}(1)$ distribution as $d$ becomes large,
this means that as $d to infty$, the distribution of $T_{n,d}$ tends to that of a Galton-Watson tree with offspring distribution $mathrm{Poisson}(1)$ conditioned to have $n$ nodes (let me write $mathrm{PGW}_n(1)$ for this distribution). The latter distribution is the same as that of a uniformly random labelled rooted tree on labels $1,ldots,n$. (At least, the latter is true once we label the Galton-Watson tree uniformly at random, or alternately remove the labels of the labelled rooted tree.)

As noted by Lyons et al. (Theorem 2.1), all this implies in particular that one can define a similar sequence $(T_n)_{n geq 1}$ such that for all $n$, $T_n$ is a subtree of $T_{n+1}$ and $T_n$ has distribution $mathrm{PGW}_n(1)$.

However, the construction in the Luczak-Winkler paper uses flows, and it is not 100% obvious how it "passes through to the $d=infty$ limit." (I say this with the caveat that I didn't make any serious attempt at figuring this out.) As a consequence, while it is known that there exists a generation procedure of the type you are looking for, I am not aware of an explicit description of the actual rule for where the leaf should be attached to $T_n$ to create $T_{n+1}$. I asked Peter Winkler about this at a conference last year and he also didn't know (though I don't know whether he had thought about this specific question in depth, either).

• Next homework - Where does meiosis II of oogenesis end exactly in tuba uterina - uterus?
• Previous Effects of Polyphasic vs Monophasic sleep in humans