Maria-Romina Ivan (Cambridge/Stanford) – The game of cops and robbers can last any ordinal amount of time

The game of cops and robbers is played on a fixed graph, with the cop choosing a vertex to start at, then the robber chooses his, and then they take turns in moving to adjacent vertices. The game ends if the cop captures the robber (lands on its vertex). What graphs allow the cop to have a winning strategy, and how long does the game typically last, assuming optimal play? For finite graphs, the situation is very well understood — the cop-win graphs are precisely constructible graphs (constructed from a single vertex by repeatedly adding dominated vertices), and the capture time can be any finite ordinal (attained for example by finite paths).

In the infinite case, not much is known. In particular, there is no structural characterisation of cop-win graphs. What about the capture time? Is there an ordinal such that for any cop-win graph the sequence of moves of an optimal game is never that ordinal?

In this talk we will explore this question by showing that the answer is surprisingly 'no'.

Joint work with Tomas Flidr.