The likely maximum size of twin subtrees in a large random tree
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929373838311424 |
|---|---|
| author | Bona, Miklos Costin, Ovidiu Pittel, Boris |
| author_facet | Bona, Miklos Costin, Ovidiu Pittel, Boris |
| contents | We call a pair of vertex-disjoint, induced subtrees of a rooted trees twins if they have the same counts of vertices by out-degrees. The likely maximum size of twins in a uniformly random, rooted Cayley tree of size $n\to\infty$ is studied. It is shown that the expected number of twins of size $(2+δ)\sqrt{\log n\cdot\log\log n}$ approaches zero, while the expected number of twins of size $(2-δ)\sqrt{\log n\cdot\log\log n}$ approaches infinity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_01190 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The likely maximum size of twin subtrees in a large random tree Bona, Miklos Costin, Ovidiu Pittel, Boris Combinatorics 05A05, 05A16, 05A15 We call a pair of vertex-disjoint, induced subtrees of a rooted trees twins if they have the same counts of vertices by out-degrees. The likely maximum size of twins in a uniformly random, rooted Cayley tree of size $n\to\infty$ is studied. It is shown that the expected number of twins of size $(2+δ)\sqrt{\log n\cdot\log\log n}$ approaches zero, while the expected number of twins of size $(2-δ)\sqrt{\log n\cdot\log\log n}$ approaches infinity. |
| title | The likely maximum size of twin subtrees in a large random tree |
| topic | Combinatorics 05A05, 05A16, 05A15 |
| url | https://arxiv.org/abs/2312.01190 |