Height of the Uniform Random Tree

291 Views Asked by At

Consider $\mathcal{T}_n$ the uniform rooted labelled tree on $n$ vertices (i.e. each spanning tree on $K_n$ has the same probability to be picked, and the root is picked uniformly among the $n$ vertices).

Denote $h(t)=\max_v d(\text{root},v)$ be the height of the tree $t$. I'm interested in understanding $h(\mathcal{T}_n)$.

While Renyi and Szekeres proved in this paper that $\mathbb{E}(\mathcal{T}_n)\to\sqrt{2\pi n}$ (and actually computed the limiting distribution of the scaled height), many authors, like Aldous in here, claim that just realizing that the height behaves like $\sqrt{n}$ should be "easy" to derive.

Does anybody know of an "easy" way to prove this? I would guess the formal fact we want to show is that $h(\mathcal{T}_n)=O(\sqrt{n})$ in probability, but this might be wrong.

Thank you very much.