Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.16571 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909010781798400 |
|---|---|
| author | Brandenberger, Anna Briend, Simon Cairns, Hannah Khanfir, Robin Kortchemski, Igor |
| author_facet | Brandenberger, Anna Briend, Simon Cairns, Hannah Khanfir, Robin Kortchemski, Igor |
| contents | Uniform attachment with freezing is an extension of the classical model of random recursive trees, in which trees are recursively built by attaching new vertices to old ones. In the model of uniform attachment with freezing, vertices are allowed to freeze, in the sense that new vertices cannot be attached to already frozen ones. We study the impact of removing attachment and/or freezing steps on the height of the trees. We show in particular that removing an attachment step can increase the expected height, and that freezing cannot substantially decrease the height of random recursive trees. Our methods are based on coupling arguments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_16571 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Does freezing impede the growth of random recursive trees? Brandenberger, Anna Briend, Simon Cairns, Hannah Khanfir, Robin Kortchemski, Igor Probability Uniform attachment with freezing is an extension of the classical model of random recursive trees, in which trees are recursively built by attaching new vertices to old ones. In the model of uniform attachment with freezing, vertices are allowed to freeze, in the sense that new vertices cannot be attached to already frozen ones. We study the impact of removing attachment and/or freezing steps on the height of the trees. We show in particular that removing an attachment step can increase the expected height, and that freezing cannot substantially decrease the height of random recursive trees. Our methods are based on coupling arguments. |
| title | Does freezing impede the growth of random recursive trees? |
| topic | Probability |
| url | https://arxiv.org/abs/2505.16571 |