Atlantic Graph Theory Seminar: Jérémie Turcotte, Université de Montréal

Progress towards the Burning Number Conjecture

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,…,k-1, and was introduced independently by Brandenburg and Scott at Intel as a transmission problem on processors and Bonato, Janssen and Roshanbin as a model for the spread of information in social networks. The Burning Number Conjecture claims that b(G)<=\lceil\sqrt{n}\rceil, where n is the number of vertices of G. This bound is tight for paths. The previous best bound for this problem, by Bastide et al., was b(G)<= \sqrt{\frac{4n}{3}}+1. We prove that the Burning Number Conjecture holds asymptotically, that is b(G)<= (1+o(1))\sqrt{n}. Following a brief introduction to graph burning, this talk will focus on the general ideas behind the proof.