Seminar: Burning Random Trees
- Date
- September 17, 2024
- Time
- 11:10 AM EDT - 12:00 PM EDT
- Location
- ENG-210 and virtually via zoom
- Open To
- All faculty, staff, students and guests are welcome to attend
- Contact
- Pawel Pralat (pralat@torontomu.ca)
Speaker: Austin Eide, TMU
Title: Burning Random Trees
Abstract: In graph burning, at each discrete time stage a vertex is chosen to burn, and the fire on every previously burning vertex spreads to all of its non-burning neighbors. The burning number $b(G)$ of a graph is the number of rounds required to burn the entire graph when burning choices are made optimally. We investigate graph burning on a critical Galton-Watson tree $T$ conditioned to have $n$ vertices; we show that, a.a.s., $b(T)$ is of the order $n^{1/3}$. Our result implies that a random tree is very likely to have burning number far below the upper bound of $\lceil n^{1/2} \rceil$ posited by the so-called Burning Number Conjecture.
(Joint work with Luc Devroye and Paweł Prałat.)
