Article ID Journal Published Year Pages File Type
4651692 Electronic Notes in Discrete Mathematics 2015 6 Pages PDF
Abstract

Let Tn be a random recursive tree with vertex set [n]:={1,…,n} and edges directed towards the root. Let degn⁡(i) denote the (in-)degree of vertex i∈[n] of Tn. Devroye and Lu [5] showed that the maximum degree Δn of Tn satisfies Δn/log2⁡n→1 a.s. Here we study the distribution of the maximum degree and of the number of vertices with near-maximum degree. For any d∈Z, let . Also, let P be a Poisson point process on R with rate function λ(x)=2−x⋅ln⁡2. We show that, up to lattice effects, the vectors converge in distribution to (|P∩[d,d+1)|,d∈Z). This recovers and extends results of Goh and Schmutz [7].

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics