Bridgewater State University
Mathematics Seminar
November 16, 2017, 3:30-4:30 PM

Speaker: Shelley Stahl
Title: Strategy Complexity for the Game of Cops and Robbers on Graphs
Abstract

Cops and Robbers is a vertex-pursuit game played on a connected graph wherein two players, a cop and a robber, begin on a pair of vertices and alternate turns moving to adjacent vertices. A graph is cop-win if, from any pair of starting vertices, the cop can occupy the same vertex as the robber after finitely many rounds. In this talk, we give a brief introduction to computability theory, and discuss computability theoretic results for the game when played on infinite computable graphs. In particular, we answer the question of whether a traditionally cop-win graph must still be cop-win if we require the cop to use a computable strategy, and explore other results regarding strategy complexity.


Return to Seminar Home Page