In-Person Talk 

Graph burning 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 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. The Burning Number Conjecture claims that b(G)<=ceil(sqrt(n)), where n is the number of vertices of G. This bound would be tight for paths. The previous best bound for this problem, by Bastide et al., was b(G)<=sqrt(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.

This is joint work with Sergey Norin.