High degrees in random recursive trees. Issue 4 (26th December 2017)

• Record Type: Journal Article
• Authors: Addario‐Berry, Louigi; Eslava, Laura
• Is Part Of: Random structures & algorithms. Volume 52:Issue 4(2018)
• Page Start: 560
• Page End: 575
• Publication Date: 2017-12-26
• Subjects: degree distributions -- extreme values -- Kingman's coalescent -- Random recursive trees; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20753
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: For n ≥ 1, let Tn be a random recursive tree (RRT) on the vertex set [ n ] = { 1, …, n } . Let deg ⁡ T n ( v ) be the degree of vertex v in Tn, that is, the number of children of v in Tn . Devroye and Lu showed that the maximum degree Δ n of Tn satisfies Δ n / ⌊ log ⁡ 2 n ⌋ → 1 almost surely; Goh and Schmutz showed distributional convergence of Δ n − ⌊ log ⁡ 2 n ⌋ along suitable subsequences. In this work we show how a version of Kingman's coalescent can be used to access much finer properties of the degree distribution in Tn . For any i ∈ ℤ, let X i ( n ) = | { v ∈ [ n ] : deg ⁡ T n ( v ) = ⌊ log ⁡ n ⌋ + i } | . Also, let P be a Poisson point process on ℝ with rate function λ ( x ) = 2 − x · ln ⁡ 2 . We show that, up to lattice effects, the vectors ( X i ( n ), i ∈ ℤ ) converge weakly in distribution to ( P [ i, i + 1 ), i ∈ ℤ ) . We also prove asymptotic normality of X i ( n ) when i = i ( n ) → − ∞ slowly, and obtain precise asymptotics for P ( Δ n − log ⁡ 2 n > i ) when i ( n ) → ∞ and i ( n ) / log ⁡ n is not too large. Our results recover and extends the previous distributional convergence results on maximal and near‐maximal degrees in RRT.