Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.14265 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910915142615040 |
|---|---|
| author | Gillott, Benjamin |
| author_facet | Gillott, Benjamin |
| contents | In the `Covering' pursuit game on a graph, a robber and a set of cops play alternately, with the cops each moving to an adjacent vertex (or not moving) and the robber moving to a vertex at distance at most 2 from his current vertex. The aim of the cops is to ensure that, after every one of their turns, there is a cop at the same vertex as the robber. How few cops are needed?
Our main aim in this paper is to consider this problem for the two-dimensional grid $[n]^2$. Bollobás and Leader asked if the number of cops needed is $o(n^2)$. We answer this question by showing that $n^{1.999}$ cops suffice. We also consider some applications. In particular we study the game `Catching a Fast Robber', concerning the number of cops needed to catch a fast robber of speed $s$ on the two-dimensional grid $[n]^2$. We improve the bounds proved by Balister, Bollobás, Narayanan and Shaw for this game. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14265 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Covering Pursuit Game Gillott, Benjamin Combinatorics 05C57 In the `Covering' pursuit game on a graph, a robber and a set of cops play alternately, with the cops each moving to an adjacent vertex (or not moving) and the robber moving to a vertex at distance at most 2 from his current vertex. The aim of the cops is to ensure that, after every one of their turns, there is a cop at the same vertex as the robber. How few cops are needed? Our main aim in this paper is to consider this problem for the two-dimensional grid $[n]^2$. Bollobás and Leader asked if the number of cops needed is $o(n^2)$. We answer this question by showing that $n^{1.999}$ cops suffice. We also consider some applications. In particular we study the game `Catching a Fast Robber', concerning the number of cops needed to catch a fast robber of speed $s$ on the two-dimensional grid $[n]^2$. We improve the bounds proved by Balister, Bollobás, Narayanan and Shaw for this game. |
| title | A Covering Pursuit Game |
| topic | Combinatorics 05C57 |
| url | https://arxiv.org/abs/2504.14265 |