Coarse geometry of the Cops and robber game

Abstract

We introduce two variations of the cops and robber game on graphs. These games yield two invariants in ${\mathbb{Z}}_{+}\cup \{\infty \}$ for any connected graph $\Gamma$, the {weak cop number $\mathsf{wcop}(\Gamma )$} and the {strong cop number $\mathsf{scop}(\Gamma )$}. These invariants satisfy that $\mathsf{scop}(\Gamma )\le \mathsf{wcop}(\Gamma )$. Any graph that is finite or a tree has strong cop number one. These new invariants are preserved under small local perturbations of the graph, specifically, both the weak and strong cop numbers are quasi-isometric invariants of connected graphs. More generally, we prove that if $\Delta$ is a quasi-retract of $\Gamma$ then $\mathsf{wcop}(\Delta )\le \mathsf{wcop}(\Gamma )$ and $\mathsf{scop}(\Delta )\le \mathsf{scop}(\Gamma )$. We exhibit families of examples of graphs with arbitrary weak cop number (resp. strong cop number). We prove that hyperbolic graphs have strong cop number one. We also prove that one-ended non-amenable locally-finite vertex-transitive graphs have infinite weak cop number. We raise the question of whether there exists a connected vertex transitive graph with finite weak (resp. strong) cop number different than one.

Version 4. Version accepted for publication in Discrete Mathematics