Large fringe trees for random trees with given vertex degrees
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |