Florian Lehner (11/09/15)

Sigurður Örn Stefánsson, September 7, 2015

Math Colloquium

Speaker: Florian Lehner
Title: Cops, robbers, and infinite graphs

Location: V-157, VRII.
Time: Friday, September 11, at 15:00-16:00.


Pursuit-evasion based searching, also known as the game of cops and robbers is a game on a graph between two players, $C$ (the cop) and $R$ (the robber). The rules are as follows: In the first round both $C$ and $R$ choose a starting vertex, in each consecutive round they are allowed to move to a neighboring vertex. The cop wins the game, if after some finite number of steps $C$ and $R$ occupy the same vertex, otherwise the robber wins.

A basic question related to this game is to characterize the class of graphs for which the cop has a winning strategy. For finite graphs it has been shown by Nowakowski and Winkler that these are exactly the constructible graphs.

For infinite graphs, Chastand et al introduced a modification of the winning criterion for which they believed the same to be true. We disprove this conjecture and explore further modifications which may lead to an extension of the result of Nowakowski and Winkler.