Probabilistic enumeration and equivalence of nonisomorphic trees
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912958750130176 |
|---|---|
| author | Stufler, Benedikt |
| author_facet | Stufler, Benedikt |
| contents | We present a new probabilistic proof of Otter's asymptotic formula for the number of unlabelled trees with a given number of vertices. We additionally prove a new approximation result, showing that the total variation distance between random Pólya trees and random unlabelled trees tends to zero when the number of vertices tends to infinity. In order to demonstrate that our approach is not restricted to trees we extend our results to tree-like classes of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_16453 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Probabilistic enumeration and equivalence of nonisomorphic trees Stufler, Benedikt Combinatorics Probability We present a new probabilistic proof of Otter's asymptotic formula for the number of unlabelled trees with a given number of vertices. We additionally prove a new approximation result, showing that the total variation distance between random Pólya trees and random unlabelled trees tends to zero when the number of vertices tends to infinity. In order to demonstrate that our approach is not restricted to trees we extend our results to tree-like classes of graphs. |
| title | Probabilistic enumeration and equivalence of nonisomorphic trees |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2305.16453 |