September 18, 2008: Seminar: Ed Reingold: "Lower Bounds for Cops and Robber Pursuit"

Abstract:

We prove that in an abstract game of cops and robber pursuit the robber can evade (that is, stay at least unit distance from) at least the floor of n/5.889 cops in an n by n continuous square region. We also show that a robber can always evade a single cop in a square with side length 4.5, and that a single cop can always capture the robber in a square with side length smaller than 2.189. In addition, we make many new observations and conjectures about both the continuous cops and robber pursuit problem and the discrete problem in which a robber tries to evade k cops on an n by n grid.