2026-07-25T12:25:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20436 2024-07-18T12:12:42Z ddc:004 open_access

Fringe Trees for Random Trees with Given Vertex Degrees Berzunza Ojeda, Gabriel Holmgren, Cecilia Janson, Svante Conditioned Galton-Watson trees fringe trees simply generated trees uniformly random trees with given vertex degrees We prove that the number of fringe subtrees, isomorphic to a given tree, in uniformly random trees with given vertex degrees, asymptotically follows a normal distribution. As an application, we establish the same asymptotic normality for random simply generated trees (conditioned Galton-Watson trees). Our approach relies on an extension of Gao and Wormald’s (2004) theorem to the multivariate setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gabriel Berzunza Ojeda and Cecilia Holmgren and Svante Janson 2024 Is Part Of LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2024.1 urn:nbn:de:0030-drops-204369 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.1 eng https://creativecommons.org/licenses/by/4.0/legalcode