Cops and Robber on Hyperbolic Manifolds

EUROCOMB’23

Abstract
The Cops and Robber game on geodesic spaces is a pursuit-evasion game with discrete steps which captures the behavior of the game played on graphs, as well as that of continuous pursuit-evasion games. One of the outstanding open problems about the game on graphs is to determine which graphs embeddable in a surface of genus $g$ have largest cop number. It is known that the cop number of genus $g$ graphs is $O(g)$ and that there are examples whose cop number is $\tilde\Omega(\sqrt{g}\,)$. The same phenomenon occurs when the game is played on geodesic surfaces. In this paper we obtain a surprising result when the game is played on a surface with constant curvature. It is shown that two cops have a strategy to come arbitrarily close to the robber, independently of the genus. For special hyperbolic surfaces we also give upper bounds on the number of cops needed to catch the robber. Our results generalize to higher-dimensional hyperbolic manifolds.

Pages:
615–622
References

M. Aigner and M. Fromme. A game of cops and robbers. Discrete Appl. Math., 8(1):1-11, 1984.
https://doi.org/10.1016/0166-218X(84)90073-8

James W Anderson. Convexity, area, and trigonometry. In Hyperbolic Geometry, pages 111-151. Springer, 1999.
https://doi.org/10.1007/978-1-4471-3987-4_5

Riccardo Benedetti and Carlo Petronio. Lectures on hyperbolic geometry. Springer Science & Business Media, 1992.
https://doi.org/10.1007/978-3-642-58158-8

Andrew Beveridge and Yiqing Cai. Two-dimensional pursuit-evasion in a compact domain with piecewise analytic boundary. ArXiv e-prints, May 2015.

Béla Bollobás, Gábor Kun, and Imre Leader. Cops and robbers in a random graph. Journal of Combinatorial Theory, Series B, 103(2):226-236, 2013.
https://doi.org/10.1016/j.jctb.2012.10.002

Anthony Bonato. An invitation to pursuit-evasion games and graph theory, volume 97 of Student Mathematical Library. American Mathematical Society, Providence, RI, 2022.
https://doi.org/10.1090/stml/097

Anthony Bonato and Richard J. Nowakowski. The game of cops and robbers on graphs, volume 61 of Student Mathematical Library. American Mathematical Society, Providence, RI, 2011.
https://doi.org/10.1090/stml/061

Nathan Bowler, Joshua Erde, Florian Lehner, and Max Pitz. Bounding the cop number of a graph by its genus. SIAM J. Discrete Math., 35(4):2459-2489, 2021.
https://doi.org/10.1137/20M1312150

Peter Bradshaw. A proof of the meyniel conjecture for abelian cayley graphs. Discrete Mathematics, 343(1):111546, 2020.
https://doi.org/10.1016/j.disc.2019.06.002

H. T. Croft. 'Lion and man': A postscript. J. Lond. Math. Soc., 39:385-390, 1964.
https://doi.org/10.1112/jlms/s1-39.1.385

Joshua Erde and Florian Lehner. Improved bounds on the cop number of a graph drawn on a surface. In Extended Abstracts EuroComb 2021, pages 111-116. Springer, 2021.
https://doi.org/10.1007/978-3-030-83823-2_18

Peter Frankl. Cops and robbers in graphs with large girth and Cayley graphs. Discrete Appl. Math., 17(3):301-305, 1987.
https://doi.org/10.1016/0166-218X(87)90033-3

Heinz Hopf. Zum Clifford-Kleinschen Raumproblem. Math. Ann., 95(1):313-339, 1926.
https://doi.org/10.1007/BF01206614

Vesna Iršič, Bojan Mohar, and Alexandra Wesolek. Cops and robber on hyperbolic manifolds. In preparation.

Vesna Iršič, Bojan Mohar, and Alexandra Wesolek. Cops and robber game in higher-dimensional manifolds with spherical and Euclidean metric. C. R. Math. Acad. Sci. Soc. R. Can., 44(3):50-68, 2022.

Gwenaël Joret, Marcin Kamiński, and Dirk Oliver Theis. The cops and robber game on graphs with forbidden (induced) subgraphs. Contrib. Discrete Math., 5(2):40-51, 2010.

Wilhelm Killing. Ueber die Clifford-Klein'schen Raumformen. Math. Ann.,39(2):257-278, 1891.
https://doi.org/10.1007/BF01206655

J. E. Littlewood. Littlewood's miscellany. Cambridge University Press, Cambridge, 1986. Edited and with a foreword by Béla Bollobás.

Tomasz Łuczak and Paweł Prałat. Chasing robbers on random graphs: zigzag theorem. Random Structures & Algorithms, 37(4):516-524, 2010.
https://doi.org/10.1002/rsa.20338

Bojan Mohar. Notes on cops and robber game on graphs. ArXiv e-prints, October 2017.

Bojan Mohar. Min-max theorem for the game of cops and robber on geodesic spaces. ArXiv e-prints, December 2021.

Bojan Mohar. The game of cops and robber on geodesic spaces. ArXiv e-prints, May 2022.

N. Yu. Satimov and A. Sh. Kuchkarov. On the solution of a model differential pursuit-evasion game on a sphere. Uzb. Mat. Zh., 2000(1):45-50, 2000.

Bernd SW Schröder. The copnumber of a graph is bounded by [3/2 genus(g)]+ 3. In Categorical perspectives, pages 243-263. Springer, 2001.
https://doi.org/10.1007/978-1-4612-1370-3_14

Stothers, Wilson. Hyperbolic geometry. http://www.maths.gla.ac.uk/wws/cabripages/hyperbolic/hyperbolic0.html. [Online; accessed 16-January-2023].

Olga Yufereva. Lion and man game in compact spaces. Dyn. Games Appl.,9(1):281-292, 2019.
https://doi.org/10.1007/s13235-018-0239-9

Metrics

0

Views

0

PDF views