Sunday, November 6, 201611:40 amNERDS: New England Recursion & Definability SeminarScience Center, Room E104‚Äč, Wellesley College, Wellesley, MA

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

Rachel Stahl

University of Connecticut

Rachel Stahl

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.

Shelley Stahl is a doctoral student at the University of Connecticut, working on a dissertation under the supervision of Reed Solomon.