Blog Archives

Topic Archive: Cops and Robbers

NERDS: New England Recursion & Definability SeminarSunday, November 6, 201611:40 amScience Center, Room E104‚Äč, Wellesley College, Wellesley, MA

Rachel Stahl

Recursion theoretic results for the game of Cops and Robbers on graphs

University of Connecticut

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, preliminary computability-theoretic and reverse-math results about the game of cops and robbers on infinite computable graphs will be discussed. We will consider several characterizations of infinite cop-win trees and graphs, and explore the complexity of winning strategies for both players.