2021/08/11 by Bóna, Miklós, Pittel, Boris · 1 citation
#05A05 #05A15 #05A16 #05C05 #05C80 #05D40 #06B05 #60C05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.04989
We prove that for any fixed k, the probability that a random vertex of a random increasing plane tree is of rank k, that is, the probability that a random vertex is at distance k from the leaves, converges to a constant ck as the size n of the tree goes to infinity. \colorblue We prove that 1-∑j≤ k ck<\tfrac3k+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 n as well. More generally, we prove that the ranks of a finite uniformly random set of vertices are asymptotically independent, each with distribution \ck\. We compute the exact value of ck for 0≤ k≤ 3, demonstrating that the limiting expected fraction of vertices with rank ≤ 3 is 0.9997…. 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 /loglog n and (1.5+\eps)log n/loglog n, \colorblue and that this rank is asymptotic to log n/loglog n with probability 1-o(1).