On the depth of depth-weighted trees
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_ | 1866917278279270400 |
|---|---|
| author | Lichev, Lyuben Linker, Amitai Lodewijks, Bas Mitsche, Dieter |
| author_facet | Lichev, Lyuben Linker, Amitai Lodewijks, Bas Mitsche, Dieter |
| contents | The depth-weighted tree DWT($f$) with weight function $f:\{0,1,2,\ldots\}\to (0,\infty)$ is a dynamic random tree grown from a root $r$ where vertices arrive consecutively and every new vertex attaches to a parent $u$ with probability proportional to $f$(distance between $u$ and $r$). This work is dedicated to a systematic analysis of the depth of DWT($f$). Namely, we provide precise analytic expressions of the typical depth of DWT($f$) for convergent, periodic, slowly growing, and (super-)exponentially growing weight functions. Furthermore, for bounded or exponentially growing $f$, we determine the typical depth up to a multiplicative constant, thus confirming and strengthening a conjecture of Leckey, Mitsche and Wormald. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15709 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the depth of depth-weighted trees Lichev, Lyuben Linker, Amitai Lodewijks, Bas Mitsche, Dieter Probability The depth-weighted tree DWT($f$) with weight function $f:\{0,1,2,\ldots\}\to (0,\infty)$ is a dynamic random tree grown from a root $r$ where vertices arrive consecutively and every new vertex attaches to a parent $u$ with probability proportional to $f$(distance between $u$ and $r$). This work is dedicated to a systematic analysis of the depth of DWT($f$). Namely, we provide precise analytic expressions of the typical depth of DWT($f$) for convergent, periodic, slowly growing, and (super-)exponentially growing weight functions. Furthermore, for bounded or exponentially growing $f$, we determine the typical depth up to a multiplicative constant, thus confirming and strengthening a conjecture of Leckey, Mitsche and Wormald. |
| title | On the depth of depth-weighted trees |
| topic | Probability |
| url | https://arxiv.org/abs/2602.15709 |