Department of Mathematical Sciences Colloquium Series

The game of Cops and Robbers

William Kinnersley Ryerson Univesity C & O Candidate

We discuss the classic Cops and Robbers game on graphs, in which a team of cops attempts to capture a robber. The game has been extensively studied, with applications ranging from video game AI to counterterrorism. It has also spawned many variants: cops in helicopters, cops with tasers, drunk robbers, and so on. When studying the game, mathematicians have traditionally asked how many cops are needed to catch the robber. In this talk, we focus on a different question that has recently gained interest: given that there are enough cops to catch the robber, how quickly can they do so? We answer this question for the n-dimensional hypercube. Along the way, we encounter a situation in which drunkenness is asymptotically optimal. This is joint work with Anthony Bonato, Przemysław Gordinowicz, and Paweł Prałat.

Monday, 18 March 2013 3:10 p.m. in Math 103 4:00 p.m. Refreshments in Math Lounge 109

Spring 2013 Colloquia & Events Schedule Mathematical Sciences | The University of Montana