×

On joint properties of vertices with a given degree or label in the random recursive tree. (English) Zbl 1504.05264

Summary: In this paper, we study the joint behaviour of the degree, depth, and label of and graph distance between high-degree vertices in the random recursive tree. We generalise the results obtained by L. Eslava [ALEA, Lat. Am. J. Probab. Math. Stat. 19, No. 1, 839–857 (2022; Zbl 1492.60020)] and extend these to include the labels of and graph distance between high-degree vertices. The analysis of both these two properties of high-degree vertices is novel, in particular in relation to the behaviour of the depth of such vertices.
In passing, we also obtain results for the joint behaviour of the degree and depth of and graph distance between any fixed number of vertices with a prescribed label. This combines several isolated results on the degree [M. Kuba and A. Panholzer, J. Comb. Theory, Ser. A 114, No. 4, 597–618 (2007; Zbl 1116.05020)], depth [M. M. Mahmoud, Probab. Eng. Inf. Sci. 5, No. 1, 53–59 (1991; Zbl 1134.68361); L. Devroye, Acta Inf. 26, No. 1–2, 123–130 (1988; Zbl 0656.68065)], and graph distance [R. P. Dobrow, J. Appl. Probab. 33, No. 3, 749–757 (1996; Zbl 0859.05037); C. Su et al., Stat. Probab. Lett. 76, No. 16, 1748–1755 (2006; Zbl 1103.05028)] of vertices with a prescribed label already present in the literature. Furthermore, we extend these results to hold jointly for any number of fixed vertices and improve these results by providing more detailed descriptions of the distributional limits.
Our analysis is based on a correspondence between the random recursive tree and a representation of the Kingman \(n\)-coalescent.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
05C07 Vertex degrees
05C12 Distance in graphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] L. Addario-Berry and L. Eslava. High degrees in random recursive trees. Random Structures & Algorithms, 52(4):560-575, 2018. · Zbl 1394.05111
[2] K. B. Athreya and S. Karlin. Embedding of urn schemes into continuous time markov branching processes and related limit theorems. The Annals of Mathematical Statistics, 39(6):1801-1817, 1968. · Zbl 0185.46103
[3] S. Banerjee and S. Bhamidi. Persistence of hubs in growing random networks. Probability Theory and Related Fields, pages 1-63, 2021.
[4] S. Bhamidi. Universal techniques to analyze preferential attachment trees: Global and local analysis. Preprint available at http://www.unc.edu/bhamidi, 2007.
[5] P. Billingsley. Convergence of probability measures. Wiley Series in Probability and Statistics, second edition, 1999. · Zbl 0944.60003
[6] D. J. Daley and D. Vere-Jones. An introduction to the theory of point processes. Vol. II. Probability and its Applications (New York). Springer, New York, second edition, 2008. General theory and structure. · Zbl 1159.60003
[7] L. Devroye. Applications of the theory of records in the study of random trees. Acta Informatica, 26(1):123-130, 1988. · Zbl 0656.68065
[8] L. Devroye and J. Lu. The strong convergence of maximal degrees in uniform random recursive trees and dags. Random Structures & Algorithms, 7(1):1-14, 1995. · Zbl 0835.05062
[9] R. P. Dobrow. On the distribution of distances in recursive trees. Journal of Applied Probability, 33(3):749-757, 1996. · Zbl 0859.05037
[10] M. Drmota. Random trees: an interplay between combinatorics and probability. Springer Science & Business Media, 2009. · Zbl 1170.05022
[11] R. Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019. · Zbl 1440.60001
[12] L. Eslava. Depth of vertices with high degree in random recursive trees. arXiv preprint 1611.07466, 2016.
[13] L. Eslava. A non-increasing tree growth process for recursive trees and applications. Combinatorics, Probability and Computing, 30(1):79-104, 2021. · Zbl 1469.60042
[14] L. Eslava, B. Lodewijks, and M. Ortgiese. Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights. Preprint, 2109.15270, 2021.
[15] Q. Feng, J. Liu, and C. Su. A note on the distance in random recursive trees. Statistics & probability letters, 76(16):1748-1755, 2006. · Zbl 1103.05028
[16] J. L. Gastwirth and P. Bhattacharya. Two probability models of pyramid or chain letter schemes demonstrating that their promotional claims are unreliable. Operations Research, 32(3):527-536, 1984. · Zbl 0544.90062
[17] W. Goh and E. Schmutz. Limit distribution for the maximum degree of a random recursive tree. Journal of computational and applied mathematics, 142(1):61-82, 2002. · Zbl 1003.05093
[18] T. Iyer. Degree distributions in recursive trees with fitnesses. Preprint, 2005.02197, 2020.
[19] S. Janson. Functional limit theorems for multitype branching processes and generalized pólya urns. Stochastic Processes and their Applications, 110(2):177-245, 2004. · Zbl 1075.60109
[20] S. Janson. Asymptotic degree distribution in random recursive trees. Random Structures & Algorithms, 26(1-2):69-83, 2005. · Zbl 1059.05094
[21] S. Janson, T. Luczak, and A. Rucinski. Random graphs. Wiley-Interscience Series, New York, 2000. · Zbl 0968.05003
[22] M. Kuba and A. Panholzer. On the degree distribution of the nodes in increasing trees. Journal of Combinatorial Theory, Series A, 114(4):597-618, 2007. · Zbl 1116.05020
[23] B. Lodewijks. Location of maximum degree vertices in weighted recursive graphs with bounded random weights. arXiv preprint 2110.00522, 2021.
[24] H. M. Mahmoud. Limiting distributions for path lengths in recursive trees. Probability in the Engineering and Informational Sciences, 5(1):53-59, 1991. · Zbl 1134.68361
[25] H. M. Mahmoud and G. S. Lueker. Evolution of random search trees, volume 200. Wiley New York, 1992. · Zbl 0762.68033
[26] H. M. Mahmoud and R. T. Smythe. Asymptotic joint normality of outdegrees of nodes in random recursive trees. Random Structures & Algorithms, 3(3):255-266, 1992. · Zbl 0767.05086
[27] A. Meir and J. Moon. Recursive trees with no nodes of out-degree one. Congressus Numerantium, 66:49-62, 1988. · Zbl 0724.05016
[28] J. W. Moon. The distance between nodes in recursive trees. London Mathematical Society Lecture Notes, 13:125-132, 1974. · Zbl 0297.05101
[29] G. O. Munsonius and L. Rüschendorf. Limit theorems for depths and distances in weighted random b-ary recursive trees. Journal of applied probability, 48(4):1060-1080, 2011. · Zbl 1234.05058
[30] H. S. Na and A. Rapoport. Distribution of nodes of a tree by degree. Mathematical Biosciences, 6:313-329, 1970. · Zbl 0193.53501
[31] D. Najock and C. Heyde. On the number of terminal vertices in certain random trees with an application to stemma construction in philology. Journal of Applied Probability, 19(3):675-680, 1982. · Zbl 0487.60012
[32] B. Pittel. Note on the heights of random recursive trees and random m-ary search trees. Random Structures & Algorithms, 5(2):337-347, 1994. · Zbl 0790.05077
[33] J. Ryvkina. Ein universeller zentraler Grenzwertsatz für den Abstand zweier Kugeln in zufälligen Splitbäumen. PhD thesis, Frankfurt am Main, Johann Wolfgang Goethe-Univ., Diplomarbeit, 2008, 2008.
[34] J. Szymanski. On the maximum degree and the height of a random recursive tree. In Random graphs, volume 87, pages 313-324, 1990. · Zbl 0747.05083
[35] A. W. van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000. · Zbl 0943.62002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.