Burning Random Trees

Abstract

Let $\mathcal{T}$ be a Galton-Watson tree with a given offspring distribution $\hat{I}¾$, where $\hat{I}¾$ is a $Z_{\ge 0}$-valued random variable with $E[\hat{I}¾]=1$ and $0<\ddot{I}{ƒ}^2:=Var[\hat{I}¾]<\infty$. For $n\ge 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}$.

12 pages