Progress towards the Burning Number Conjecture

Graph Theory Seminar
Tuesday, October 11, 2022 - 3:45pm for 1 hour (actually 50 minutes)
Jérémie Turcotte – McGill University – mail@jeremieturcotte.com
Tom Kelly

The burning number $b(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ can be covered by $k$ balls of radii respectively $0,\dots,k-1$, and was introduced independently by Brandenburg and Scott at Intel as a transmission problem on processors \cite{alon} and Bonato, Janssen and Roshanbin as a model for the spread of information in social networks.

The Burning Number Conjecture \cite{bonato} claims that $b(G)\leq \left\lceil\sqrt{n}\right\rceil$, where $n$ is the number of vertices of $G$. This bound tight for paths. The previous best bound for this problem, by Bastide et al. \cite{bastide}, was $b(G)\leq \sqrt{\frac{4n}{3}}+1$.

We prove that the Burning Number Conjecture holds asymptotically, that is $b(G)\leq (1+o(1))\sqrt{n}$.

Following a brief introduction to graph burning, this talk will focus on the general ideas behind the proof.