Chasing Robbers on Random Geometric Graphs: A Geometric Approach
Abstract
We study the vertex pursuit game of Cops and Robbers, in which cops try to capture a robber on the vertices of a graph. The minimum number of cops required to win on a given graph $G$ is called the cop number of $G$. We focus on $G_{d}(n,r)$, a random geometric graph in which $n$ vertices are chosen uniformly at random and independently from $[0,1]^d$, and two vertices are adjacent if the Euclidean distance between them is at most $r$. The main result is that if $r^{3d-1}>c_d \frac{\log n}{n}$ then the cop number is 1 with probability that tends to 1 as $n$ tends to infinity. Our method provides a tight $O(1/r^2)$ upper bound for the number of rounds needed to catch the robber.
Introduction
The game of Cops and Robbers is a fundamental pursuit-evasion problem in graph theory. Played on a graph $G$, a set of cops and a single robber occupy vertices and take turns moving along edges. The cops win if they can land on the same vertex as the robber; the robber wins if they can evade capture indefinitely. The central question is the "cop number" $c(G)$, the minimum number of cops needed to guarantee a win.
While much research has focused on deterministic graphs or Erdős–Rényi random graphs, this paper investigates Random Geometric Graphs (RGGs), denoted $G_d(n, r)$. These graphs are generated by placing $n$ points in a $d$-dimensional unit cube and connecting pairs within distance $r$. RGGs are particularly relevant for modeling physical networks like sensor arrays or social clusters where spatial proximity dictates connectivity. The challenge addressed here is determining the conditions under which a single cop is sufficient to win and how long that capture takes.
The Pursuit Strategy: Continuous to Discrete
The authors introduce a novel approach by first solving the game in a continuous setting. Imagine the game played on a continuous unit cube. The cop's strategy is to start at the center $O$ and, in each round, move to a point $C'$ on the line segment $OR'$, where $R'$ is the robber's current position.
Geometric Monotonicity
The key insight is "Geometric Monotonicity." By moving outward from the center while staying on the line to the robber, the cop ensures that the square of their distance from the center increases by at least $r^2/5$ in each step (unless they catch the robber immediately). This forces the robber toward the boundaries or directly into the cop's reach. Because the unit cube has a finite diameter, this outward progress must eventually result in capture.
Discretization and Shadowing
To apply this continuous strategy to a discrete graph $G_d(n, r)$, the authors use a "shadowing" technique. The cop on the graph attempts to stay as close as possible to the ideal position dictated by the continuous strategy.
For this shadowing to be successful, the graph must be dense enough so that a vertex always exists near the ideal continuous position. The authors prove a geometric lemma: if $r^{3d-1} > c_d \frac{\log n}{n}$, then with high probability, every "thin triangle" (or cone in higher dimensions) of a specific size and shape within the unit cube contains at least one vertex. These triangles represent the possible "next steps" for the cop. By ensuring these triangles are populated, the cop can always find a vertex that maintains the required distance progress.
Key Results and Capture Time
The primary result is that for any dimension $d \geq 2$, a single cop is sufficient to win on $G_d(n, r)$ asymptotically almost surely (a.a.s.) under the specified density condition. This generalizes earlier results for $d=2$ and provides a more robust proof technique.
Furthermore, the authors establish a tight upper bound of $O(1/r^2)$ for the number of rounds required for capture. This bound is intuitive: since the cop gains roughly $r^2$ in squared distance each round and the total squared distance to the boundary is constant, the number of steps should scale with $1/r^2$. The authors also prove that the robber can evade for at least $\Omega(1/r^2)$ steps, confirming the tightness of the bound.
Conclusion and Future Work
This work provides a geometrically intuitive alternative to previous proofs that relied on the structural property of "dismantlability." By shifting the focus from graph structure to geometric progress, the authors offer a framework that easily generalizes to higher dimensions.
While the paper establishes a strong upper bound for the cop number in dense RGGs, several avenues for future research remain. The authors explicitly state they made no attempt to optimize the absolute constants ($c_d$) in their formulas. Additionally, investigating the cop number in the sparse regime—specifically near the connectivity threshold of the graph—remains an open and interesting challenge. Finally, while the strategy works for the unit cube, different approaches might be required for more complex geometric domains with irregular boundaries.
Summary updated