Graph Searching Games and Probabilistic Methods

The intersection of graph searching and probabilistic methods is a new topic within graph theory, with applications to graph searching problems such as the game of Cops and Robbers and its many variants, Firefighting, graph burning, and acquaintance time. Graph searching games may be played on random structures such as binomial random graphs, random regular graphs or random geometric graphs. Probabilistic methods may also be used to understand the properties of games played on deterministic structures. A third and new approach is where randomness figures into the rules of the game, such as in the game of Zombies and Survivors. We give a broad survey of graph searching and probabilistic methods, highlighting the themes and trends in this emerging area. The talk is based on my upcoming book (with the same title) co-authored with Pawel Pralat (to be published by CRC Press in late 2017).