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

Seminar Announcement


Lower Bounds for Cops and Robber Pursuit

Ed Reingold
Illinois Institute of Technology
Thursday, September 25, 2008
11:00 a.m., 1000 SEO


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.



Host: Professor Tanya Berger-Wolf












































 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF