Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651692 | Electronic Notes in Discrete Mathematics | 2015 | 6 Pages |
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/log2n→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⋅ln2. 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