Random increasing plane trees: asymptotic enumeration of vertices by distance from leaves

Miklós Bóna, Boris Pittel

Published 2021-08-11Version 1

We prove that for any fixed $k$, the probability that a random vertex of a random increasing plane tree is of rank $k$, i.e. at vertex-distance $k$ from the leaves, converges to a constant $c_k$ as the size $n$ of the tree goes to infinity. We prove a similar result for randomly selected $r$-tuples of vertices that shows that the ranks of a finite uniformly random set of vertices are asymptotically independent. We compute the exact value of $c_k$ for $0\leq k\leq 3$, demonstrating that the limiting expected fraction of vertices with rank $\le 3$ is $0.9997\dots$. In general, the distribution $\{c_k\}$ is quasi-Poisson, i.e. $c_k=O(1/(k-2)!)$. We prove that with high probability, the highest rank of a vertex in the tree is sandwiched between $\log n / (\log(\log n))$ and $1.5\log n/(\log(\log n))$.