How to hunt an invisible rabbit on an infinite graph in finite time

Abstract:

In this talk we will look at a discrete hidden movement game where a hunter tries to catch an invisible rabbit on an infinite graph in finite time. The rabbit is located on the nodes of the graph and after each shot of the hunter the rabbit scampers startled into a neighboring node. In the setting, we will look at the question of how a graph must be constructed so that the hunter can safely catch the rabbit in finite time regardless of the unknown starting position and route of the rabbit. In particular, we will find a characterization of all graphs with possibly infinitely many nodes where the hunter has such a winning strategy. We will also look at a variant where the rabbit is deaf and therefore does not always move.