{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:58:56Z","timestamp":1747173536670,"version":"3.40.5"},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T00:00:00Z","timestamp":1712880000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The protection number of a vertex <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000099_inline1.png\"\/><jats:tex-math>\n$v$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in a tree is the length of the shortest path from <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000099_inline2.png\"\/><jats:tex-math>\n$v$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> to any leaf contained in the maximal subtree where <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000099_inline3.png\"\/><jats:tex-math>\n$v$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the root. In this paper, we determine the distribution of the maximum protection number of a vertex in simply generated trees, thereby refining a recent result of Devroye, Goh, and Zhao. Two different cases can be observed: if the given family of trees allows vertices of outdegree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548324000099_inline4.png\"\/><jats:tex-math>\n$1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then the maximum protection number is on average logarithmic in the tree size, with a discrete double-exponential limiting distribution. If no such vertices are allowed, the maximum protection number is doubly logarithmic in the tree size and concentrated on at most two values. These results are obtained by studying the singular behaviour of the generating functions of trees with bounded protection number. While a general distributional result by Prodinger and Wagner can be used in the first case, we prove a variant of that result in the second case.<\/jats:p>","DOI":"10.1017\/s0963548324000099","type":"journal-article","created":{"date-parts":[[2024,4,12]],"date-time":"2024-04-12T07:37:57Z","timestamp":1712907477000},"page":"518-553","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["The distribution of the maximum protection number in simply generated trees"],"prefix":"10.1017","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0082-7334","authenticated-orcid":false,"given":"Clemens","family":"Heuberger","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0566-4047","authenticated-orcid":false,"given":"Sarah J.","family":"Selkirk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5533-2764","authenticated-orcid":false,"given":"Stephan","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,4,12]]},"reference":[{"key":"S0963548324000099_ref1","doi-asserted-by":"publisher","DOI":"10.1090\/mmono\/058"},{"key":"S0963548324000099_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-211-75357-6"},{"key":"S0963548324000099_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2011.11.017"},{"key":"S0963548324000099_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2013.09.003"},{"key":"S0963548324000099_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2007.07.001"},{"key":"S0963548324000099_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-017-1772-9"},{"key":"S0963548324000099_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548322000128"},{"key":"S0963548324000099_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2012.06.005"},{"key":"S0963548324000099_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/apr.2017.24"},{"key":"S0963548324000099_ref19","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1429282623"},{"key":"S0963548324000099_ref12","doi-asserted-by":"publisher","DOI":"10.2298\/AADM190329010G"},{"key":"S0963548324000099_ref16","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v20-3627"},{"key":"S0963548324000099_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2010.10.045"},{"key":"S0963548324000099_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"S0963548324000099_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975505.5"},{"key":"S0963548324000099_ref11","unstructured":"[11] Gaither, J. , Homma, Y. , Sellke, M. and Ward, M. D . On the number of 2-protected nodes in tries and suffix trees. In 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA\u201912) (N. Broutin and L. Devroye, eds), Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, pp. 381\u2013398."},{"key":"S0963548324000099_ref15","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v20-3577"},{"key":"S0963548324000099_ref7","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v19-3048"},{"key":"S0963548324000099_ref17","doi-asserted-by":"publisher","DOI":"10.1214\/11-PS188"},{"key":"S0963548324000099_ref14","doi-asserted-by":"publisher","DOI":"10.2298\/AADM1702314H"},{"key":"S0963548324000099_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2016.01.001"},{"key":"S0963548324000099_ref22","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1978-085-0"},{"key":"S0963548324000099_ref23","first-page":"123","article-title":"Bootstrapping and double-exponential limit laws","volume":"17","author":"Prodinger","year":"2015","journal-title":"Discrete Math. Theor. Comput. Sci."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548324000099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T16:08:29Z","timestamp":1728403709000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548324000099\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,12]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["S0963548324000099"],"URL":"https:\/\/doi.org\/10.1017\/s0963548324000099","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2024,4,12]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}