Burning Random Trees
| Autor: | Devroye, Luc, Eide, Austin, Pralat, Pawel |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Let $\mathcal{T}$ be a Galton-Watson tree with a given offspring distribution $\xi$, where $\xi$ is a $Z_{\geq 0}$-valued random variable with $E[\xi] = 1$ and $0 < \sigma^{2}:=Var[\xi] < \infty$. For $n \geq 1$, let $T_{n}$ be the tree $\mathcal{T}$ conditioned to have $n$ vertices. In this paper we investigate $b(T_n)$, the burning number of $T_n$. Our main result shows that asymptotically almost surely $b(T_n)$ is of the order of $n^{1/3}$. Comment: 11 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|