Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.03464 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916931264577536 |
|---|---|
| author | Fontenot, Kenzie Nguyen, Iris Olsen, Cody |
| author_facet | Fontenot, Kenzie Nguyen, Iris Olsen, Cody |
| contents | The game of Cops and Robbers is a pursuit-evasion game on graphs that has been extensively studied in finite settings, particularly through the concept of cop number. In this paper, we explore infinite variants of the game, focusing on the lattice graph $\mathbb{Z}^n$. Since the cop number of $\mathbb{Z}^n$ is infinite, we shift attention to the notion of \emph{cop density}, examining how sparsely cops may be placed while still guaranteeing capture. We introduce the framework of \emph{coordinate matching} as a central strategy and prove the existence of density-zero configurations of cops that ensure eventual capture of the robber. Building on this, we provide a complete classification of winning cop sets in $\mathbb{Z}^n$, showing necessary and sufficient conditions for capture based on infinite distributions of cops across coordinate directions. We conclude with directions for further study, including variations of the game where the robber imposes spatial restrictions on cop placement. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_03464 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Classification of Winning Sets of Cops in $\mathbb{Z}^n$ Fontenot, Kenzie Nguyen, Iris Olsen, Cody Combinatorics 05C57 The game of Cops and Robbers is a pursuit-evasion game on graphs that has been extensively studied in finite settings, particularly through the concept of cop number. In this paper, we explore infinite variants of the game, focusing on the lattice graph $\mathbb{Z}^n$. Since the cop number of $\mathbb{Z}^n$ is infinite, we shift attention to the notion of \emph{cop density}, examining how sparsely cops may be placed while still guaranteeing capture. We introduce the framework of \emph{coordinate matching} as a central strategy and prove the existence of density-zero configurations of cops that ensure eventual capture of the robber. Building on this, we provide a complete classification of winning cop sets in $\mathbb{Z}^n$, showing necessary and sufficient conditions for capture based on infinite distributions of cops across coordinate directions. We conclude with directions for further study, including variations of the game where the robber imposes spatial restrictions on cop placement. |
| title | A Classification of Winning Sets of Cops in $\mathbb{Z}^n$ |
| topic | Combinatorics 05C57 |
| url | https://arxiv.org/abs/2509.03464 |