Catching a fast robber on the grid. (English) Zbl 1369.05145
Summary: We study the problem of cops and robbers on the grid where the robber is allowed to move faster than the cops. It is well known that two cops are necessary and sufficient to catch the robber on any finite grid when the robber has unit speed. Here, we prove that if the speed of the robber exceeds a sufficiently large absolute constant, then the number of cops needed to catch the robber on an \(n \times n\) grid is \(\exp(\Omega(\log n / \log \log n))\).
MSC:
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 91A43 | Games involving graphs |
| 91A24 | Positional games (pursuit and evasion, etc.) |
References:
| [1] | Alon, N.; Mehrabian, A., On a generalization of Meyniel’s conjecture on the Cops and Robbers game, Electron. J. Combin., 18 (2011), Paper 19 · Zbl 1205.05159 |
| [2] | Baird, William; Bonato, Anthony, Meyniel’s conjecture on the cop number: a survey, J. Comb., 3, 225-238 (2012) · Zbl 1276.05074 |
| [3] | Bollobás, B.; Leader, I., The angel and the devil in three dimensions, J. Combin. Theory Ser. A, 113, 176-184 (2006) · Zbl 1145.91322 |
| [4] | Bowditch, B. H., The angel game in the plane, Combin. Probab. Comput., 16, 345-362 (2007) · Zbl 1222.91011 |
| [5] | Fomin, F. V.; Golovach, P. A.; Kratochvíl, J.; Nisse, N.; Suchan, K., Pursuing a fast robber on a graph, Theoret. Comput. Sci., 411, 1167-1181 (2010) · Zbl 1192.91027 |
| [6] | Frieze, A.; Krivelevich, M.; Loh, P., Variations on cops and robbers, J. Graph Theory, 69, 383-402 (2012) · Zbl 1243.05165 |
| [7] | Gacs, P., The angel wins, preprint |
| [8] | Kutz, M., Conway’s angel in three dimensions, Theoret. Comput. Sci., 349, 443-451 (2005) · Zbl 1121.91025 |
| [9] | Lu, L.; Peng, X., On Meyniel’s conjecture of the cop number, J. Graph Theory, 71, 192-205 (2012) · Zbl 1248.05121 |
| [10] | Maamoun, M.; Meyniel, H., On a game of policemen and robber, Discrete Appl. Math., 17, 307-309 (1987) · Zbl 0615.05049 |
| [11] | Máthé, A., The angel of power 2 wins, Combin. Probab. Comput., 16, 363-374 (2007) · Zbl 1222.91012 |
| [12] | Mehrabian, A., Lower bounds for the cop number when the robber is fast, Combin. Probab. Comput., 20, 617-621 (2011) · Zbl 1223.05191 |
| [13] | Nisse, N.; Suchan, K., Fast robber in planar graphs, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol. 5344 (2008), Springer: Springer Berlin, Heidelberg), 312-323 · Zbl 1202.68286 |
| [14] | Nowakowski, R.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 235-239 (1983) · Zbl 0508.05058 |
| [15] | Quilliot, A., Jeux et pointes fixes sur les graphes (1978), Université de Paris VI, Ph.D. thesis |
| [16] | Scott, A.; Sudakov, B., A bound for the cops and robbers problem, SIAM J. Discrete Math., 25, 1438-1442 (2011) · Zbl 1237.05132 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
