کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651692 1632581 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
High degrees in recursive trees
ترجمه فارسی عنوان
درجه بالا در درختان بازگشتی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 50, December 2015, Pages 451-456