{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T11:18:43Z","timestamp":1762341523287},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T00:00:00Z","timestamp":1603065600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce a non-increasing tree growth process <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000073_inline1.png\" \/><jats:tex-math>\n$((T_n,{\\sigma}_n),\\, n\\ge 1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> is a rooted labelled tree on <jats:italic>n<\/jats:italic> vertices and <jats:italic>\u03c3<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> is a permutation of the vertex labels. The construction of (<jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, <jats:italic>\u03c3<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>) from (<jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>\u22121<\/jats:sub>, <jats:italic>\u03c3<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>\u22121<\/jats:sub>) involves rewiring a random (possibly empty) subset of edges in <jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>\u22121<\/jats:sub> towards the newly added vertex; as a consequence <jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>\u22121<\/jats:sub> \u2284 <jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> with positive probability. The key feature of the process is that the shape of <jats:italic>T<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> has the same law as that of a random recursive tree, while the degree distribution of any given vertex is not monotone in the process.<\/jats:p><jats:p>We present two applications. First, while couplings between Kingman\u2019s coalescent and random recursive trees were known for any fixed <jats:italic>n<\/jats:italic>, this new process provides a non-standard coupling of all finite Kingman\u2019s coalescents. Second, we use the new process and the Chen\u2013Stein method to extend the well-understood properties of degree distribution of random recursive trees to extremal-range cases. Namely, we obtain convergence rates on the number of vertices with degree at least <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000073_inline2.png\" \/><jats:tex-math>\n$c\\ln n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, <jats:italic>c<\/jats:italic> \u2208 (1, 2), in trees with <jats:italic>n<\/jats:italic> vertices. Further avenues of research are discussed.<\/jats:p>","DOI":"10.1017\/s0963548320000073","type":"journal-article","created":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T08:38:45Z","timestamp":1603096725000},"page":"79-104","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":4,"title":["A non-increasing tree growth process for recursive trees and applications"],"prefix":"10.1017","volume":"30","author":[{"given":"Laura","family":"Eslava","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,10,19]]},"reference":[{"key":"S0963548320000073_ref3","doi-asserted-by":"publisher","DOI":"10.2307\/3212152"},{"key":"S0963548320000073_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20011"},{"key":"S0963548320000073_ref22","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1998.2919"},{"key":"S0963548320000073_ref6","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF00265991","article-title":"Branching processes in the analysis of the heights of trees","volume":"24","author":"Devroye","year":"1987","journal-title":"Acta Inform."},{"key":"S0963548320000073_ref15","first-page":"115","article-title":"Les valeurs extr\u00eames des distributions statistiques","volume":"5","author":"Gumbel","year":"1935","journal-title":"Ann. Inst. H. Poincar\u00e9"},{"key":"S0963548320000073_ref10","unstructured":"[10] Eslava, L. (2016) Depth of vertices with high degree in random recursive trees. arXiv:1611.07466"},{"key":"S0963548320000073_ref1","doi-asserted-by":"crossref","unstructured":"[1] Addario-Berry, L. (2015) Partition functions of discrete coalescents: from Cayley\u2019s formula to Frieze\u2019s \u03b6 (3) limit theorem. In XI Symposium on Probability and Stochastic Processes, Vol. 68 of Progress in Probability, Birkh\u00e4user.","DOI":"10.1007\/978-3-319-13984-5_1"},{"key":"S0963548320000073_ref24","volume-title":"Data Structure Techniques","author":"Standish","year":"1980"},{"key":"S0963548320000073_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548320000073_ref23","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1002\/rsa.3240050207","article-title":"Note on the heights of random recursive trees and random m-ary search trees","volume":"5","author":"Pittel","year":"1994","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000073_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20046"},{"key":"S0963548320000073_ref9","unstructured":"[9] Durrett, R. (1996) Probability: Theory and Examples, second edition, Duxbury."},{"key":"S0963548320000073_ref21","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0025-5564(70)90071-4","article-title":"Distribution of nodes of a tree by degree","volume":"6","author":"Na","year":"1970","journal-title":"Math. Biosci."},{"key":"S0963548320000073_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00285-009-0275-6"},{"key":"S0963548320000073_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M"},{"key":"S0963548320000073_ref14","unstructured":"[14] Goldschmidt, C. (2000) The Chen\u2013Stein method for convergence of distributions. https:\/\/www.stats.ox.ac.uk\/~goldschm\/chen-stein.ps.gz"},{"key":"S0963548320000073_ref12","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1017\/S0963548308009243","article-title":"Subtree sizes in recursive trees and binary search trees: Berry\u2013Esseen bounds and Poisson approximations","volume":"17","author":"Fuchs","year":"2008","journal-title":"Combin. Probab. Comput."},{"key":"S0963548320000073_ref19","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v4-1005"},{"key":"S0963548320000073_ref7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/rsa.3240070102","article-title":"The strong convergence of maximal degrees in uniform random recursive trees and dags","volume":"7","author":"Devroye","year":"1995","journal-title":"Random Struct. Algorithms"},{"key":"S0963548320000073_ref16","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v20-3627"},{"key":"S0963548320000073_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20753"},{"key":"S0963548320000073_ref13","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0377-0427(01)00460-5","article-title":"Limit distribution for the maximum degree of a random recursive tree","volume":"142","author":"Goh","year":"2002","journal-title":"J. Comput. Appl. Math."},{"key":"S0963548320000073_ref18","volume-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","author":"Janson","year":"2000"},{"key":"S0963548320000073_ref4","doi-asserted-by":"publisher","DOI":"10.1214\/105051606000000547"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000073","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T11:50:54Z","timestamp":1611229854000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000073\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,19]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["S0963548320000073"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000073","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,19]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}