Graph Searching Games and Probabilistic Methods
Pawel Pralat, Ryerson University, presents their seminar
The application of probabilistic methods to graph searching problems such as the game of Cops and Robbers and Firefighting is a new topic within graph theory. Research on this topic emerged only over the last few years, and as such, it represents a rapidly evolving and dynamic area. Probability enters the picture in three different ways: 1) graph searching games can be played on random graphs; 2) one of the players can make random moves; 3) probabilistic methods can be used to prove results about deterministic games. During the talk, I will show a few examples from each class.