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

preprint2022arXivOpen access

Abstract

We prove that for any fixed kk, the probability that a random vertex of a random increasing plane tree is of rank kk, that is, the probability that a random vertex is at distance kk from the leaves, converges to a constant ckc_k as the size nn of the tree goes to infinity. {\color{blue} We prove that 1−∑j≤kck<3k+1(2k+1)!1-\sum_{j\le k} c_k<\tfrac{3^{k+1}}{(2k+1)!}, so that the tail of the limiting rank distribution is super-exponentially narrow. We prove that the latter property holds uniformly for all finite nn as well.} More generally, we prove that the ranks of a finite uniformly random set of vertices are asymptotically independent, each with distribution {ck}\{c_k\}. We compute the exact value of ckc_k for 0≤k≤30\leq k\leq 3, demonstrating that the limiting expected fraction of vertices with rank ≤3\le 3 is 0.9997…0.9997\dots. We show that with probability $1-n^{-0.99\eps}$ the highest rank of a vertex in the tree is sandwiched between $(1-\eps)\log n /\log\log n$ and $(1.5+\eps)\log n/\log\log n$, {\color{blue} and that this rank is asymptotic to log⁡n/log⁡log⁡n\log n/\log\log n with probability 1−o(1)1-o(1).}

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.