Large fringe trees for random trees with given vertex degrees

Fuente: arXiv
Gespeichert in:
Bibliographische Detailangaben
Hauptverfasser: Ojeda, Gabriel Berzunza, Holmgren, Cecilia, Janson, Svante
Format: Preprint
Veröffentlicht: 2026
Schlagworte:
Online-Zugang:
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
_version_ 1866917388479365120
author Ojeda, Gabriel Berzunza
Holmgren, Cecilia
Janson, Svante
author_facet Ojeda, Gabriel Berzunza
Holmgren, Cecilia
Janson, Svante
contents This paper extends the study of fringe trees in random plane trees with a given degree statistic. While previous work established the asymptotic normality of the count of fringe trees isomorphic to a fixed tree, we investigate the case where the target tree grows with the size of the random tree. We consider three primary subtree counts: the number of fringe trees isomorphic to a specific growing tree, the number of fringe trees sharing a given growing degree statistic, and the number of fringe trees of a specific growing size. To establish our results, we employ and compare four distinct probabilistic frameworks: the method of moments with the Gao-Wormald theorem, Stein's method with coupling (to provide explicit error bounds in total variation distance), the Cai-Devroye method, and Stein's method with exchangeable pairs. Our findings provide conditions for Poisson and normal convergence for these subtree counts. Additionally, we provide a local limit theorem for sums of values obtained via sampling without replacement that may be of independent interest. Finally, our results and methods are also applied to conditioned critical Galton-Watson trees.
format Preprint
id arxiv_https___arxiv_org_abs_2604_06012
institution arXiv
publishDate 2026
record_format arxiv
spellingShingle Large fringe trees for random trees with given vertex degrees
Ojeda, Gabriel Berzunza
Holmgren, Cecilia
Janson, Svante
Probability
Combinatorics
This paper extends the study of fringe trees in random plane trees with a given degree statistic. While previous work established the asymptotic normality of the count of fringe trees isomorphic to a fixed tree, we investigate the case where the target tree grows with the size of the random tree. We consider three primary subtree counts: the number of fringe trees isomorphic to a specific growing tree, the number of fringe trees sharing a given growing degree statistic, and the number of fringe trees of a specific growing size. To establish our results, we employ and compare four distinct probabilistic frameworks: the method of moments with the Gao-Wormald theorem, Stein's method with coupling (to provide explicit error bounds in total variation distance), the Cai-Devroye method, and Stein's method with exchangeable pairs. Our findings provide conditions for Poisson and normal convergence for these subtree counts. Additionally, we provide a local limit theorem for sums of values obtained via sampling without replacement that may be of independent interest. Finally, our results and methods are also applied to conditioned critical Galton-Watson trees.
title Large fringe trees for random trees with given vertex degrees
topic Probability
Combinatorics
url https://arxiv.org/abs/2604.06012