{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T08:27:06Z","timestamp":1712910426298},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study several parameters of a random Bienaym\u00e9\u2013Galton\u2013Watson tree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline1.png\" \/><jats:tex-math>\n$T_n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of size <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline2.png\" \/><jats:tex-math>\n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> defined in terms of an offspring distribution <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline3.png\" \/><jats:tex-math>\n$\\xi$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with mean <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline4.png\" \/><jats:tex-math>\n$1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and nonzero finite variance <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline5.png\" \/><jats:tex-math>\n$\\sigma ^2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline6.png\" \/><jats:tex-math>\n$f(s)=\\mathbb{E}\\{s^\\xi \\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be the generating function of the random variable <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline7.png\" \/><jats:tex-math>\n$\\xi$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We show that the independence number is in probability asymptotic to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline8.png\" \/><jats:tex-math>\n$qn$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline9.png\" \/><jats:tex-math>\n$q$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the unique solution to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline10.png\" \/><jats:tex-math>\n$q = f(1-q)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. One of the many algorithms for finding the largest independent set of nodes uses a notion of repeated peeling away of all leaves and their parents. The number of rounds of peeling is shown to be in probability asymptotic to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline11.png\" \/><jats:tex-math>\n$\\log n\/\\log (1\/f'(1-q))$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Finally, we study a related parameter which we call the leaf-height. Also sometimes called the protection number, this is the maximal shortest path length between any node and a leaf in its subtree. If <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline12.png\" \/><jats:tex-math>\n$p_1 = \\mathbb{P}\\{\\xi =1\\}\\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then we show that the maximum leaf-height over all nodes in <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline13.png\" \/><jats:tex-math>\n$T_n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is in probability asymptotic to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline14.png\" \/><jats:tex-math>\n$\\log n\/\\log (1\/p_1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. If <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline15.png\" \/><jats:tex-math>\n$p_1 = 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline16.png\" \/><jats:tex-math>\n$\\kappa$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the first integer <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline17.png\" \/><jats:tex-math>\n$i\\gt 1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline18.png\" \/><jats:tex-math>\n$\\mathbb{P}\\{\\xi =i\\}\\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then the leaf-height is in probability asymptotic to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000128_inline19.png\" \/><jats:tex-math>\n$\\log _\\kappa \\log n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548322000128","type":"journal-article","created":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T12:08:39Z","timestamp":1654776519000},"page":"68-90","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["On the peel number and the leaf-height of Galton\u2013Watson trees"],"prefix":"10.1017","volume":"32","author":[{"given":"Luc","family":"Devroye","sequence":"first","affiliation":[]},{"given":"Marcel K.","family":"Goh","sequence":"additional","affiliation":[]},{"given":"Rosie Y.","family":"Zhao","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2022,6,9]]},"reference":[{"key":"S0963548322000128_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20921"},{"key":"S0963548322000128_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/1106009"},{"key":"S0963548322000128_ref22","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1429282623"},{"key":"S0963548322000128_ref1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005936"},{"key":"S0963548322000128_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2011.11.017"},{"key":"S0963548322000128_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.12.013"},{"key":"S0963548322000128_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90004-6"},{"key":"S0963548322000128_ref15","doi-asserted-by":"publisher","DOI":"10.1214\/11-PS188"},{"key":"S0963548322000128_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2013.09.003"},{"key":"S0963548322000128_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20568"},{"key":"S0963548322000128_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-017-1772-9"},{"key":"S0963548322000128_ref2","unstructured":"[2] Alsmeyer, G. (2008) Galton\u2013Watson Processes. Course notes at the University of M\u00fcnster."},{"key":"S0963548322000128_ref19","volume-title":"Random Mappings","author":"Kolchin","year":"1986"},{"key":"S0963548322000128_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20259"},{"key":"S0963548322000128_ref20","volume-title":"Probability on Trees and Networks","author":"Lyons","year":"2017"},{"key":"S0963548322000128_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2012.06.005"},{"key":"S0963548322000128_ref25","first-page":"155","article-title":"Local limits of large Galton\u2013Watson trees rerooted at a random vertex","volume":"55","author":"Stufler","year":"2019","journal-title":"Ann. l\u2019Inst. Henri Poincar\u00e9 Probab. Stat."},{"key":"S0963548322000128_ref11","doi-asserted-by":"publisher","DOI":"10.2307\/3212112"},{"key":"S0963548322000128_ref18","first-page":"425","article-title":"Subdiffusive behavior of a random walk on a random cluster","volume":"22","author":"Kesten","year":"1986","journal-title":"Ann. l\u2019Inst. Henri Poincar\u00e9"},{"key":"S0963548322000128_ref14","unstructured":"[14] Gittenberger, B. , Go\u0142\u0229biewski, Z. , Larcher, I. and Sulkowska, M. . \u201cProtection numbers in simply generated trees and P\u00f3lya trees,\u201d. arXiv preprint 1904. 03519, 2019."},{"key":"S0963548322000128_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2010.10.045"},{"key":"S0963548322000128_ref17","unstructured":"[17] Kersting, G. . \u201cOn the height profile of a conditioned Galton\u2013Watson tree,\u201d. arXiv preprint 1101. 3656, 1998."},{"key":"S0963548322000128_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.02.024"},{"key":"S0963548322000128_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-65371-1"},{"key":"S0963548322000128_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2007.07.001"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000128","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T05:08:24Z","timestamp":1671512904000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000128\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["S0963548322000128"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000128","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}