Cop number of random k-uniform hypergraphs

EUROCOMB’23

Joshua Erde Mihyun Kang Florian Lehner Bojan Mohar Dominik Schmid

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-058

PDF
Abstract
The game of Cops and Robber is usually played on a graph, in which a group of cops attempt to catch a robber moving along the edges of the graph. The cop number of a graph is the minimum number of cops required to win the game. An important conjecture in this area, due to Meyniel, states that the cop number of an $n$-vertex connected graph is $O(\sqrt{n})$. In 2016, Prałat and Wormald [Meyniel‘s conjecture holds for random graphs, Random Structures Algorithms. 48 (2016), no. 2, 396–421. MR3449604] showed that this conjecture holds with high probability for random graphs above the connectedness threshold. Moreoever, Łuczak and Prałat [Chasing robbers on random graphs: Zigzag theorem, Random Structures Algorithms. 37 (2010), no. 4, 516–524. MR2760362] showed that on a $\log$-scale the cop number demonstrates a surprising zigzag behaviour in dense regimes of the binomial random graph $G(n,p)$. In this paper, we consider the game of Cops and Robber on a hypergraph, where the players move along hyperedges instead of edges. We show that with high probability the cop number of the $k$-uniform binomial random hypergraph $G^k(n,p)$ is $O\left(\sqrt{\frac{n}{k}} \log n \right)$ for a broad range of parameters $p$ and $k$. As opposed to the case of $G(n,p)$, on a $\log$-scale our upper bound on the cop number arises as the minimum of two complementary zigzag curves. Furthermore, we conjecture that the cop number of a connected $k$-uniform hypergraph on $n$ vertices is $O\left(\sqrt{\frac{n}{k}}\right)$.

Pages:
416–424
References

I. Adler. Marshals, monotone marshals, and hypertree-width. J. Graph Theory, 47(4):275-296, 2004.
https://doi.org/10.1002/jgt.20025

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

T. Andreae. On a pursuit game played on graphs for which a minor is excluded. Journal of Combinatorial Theory, Series B, 41(1):37-47, 1986.
https://doi.org/10.1016/0095-8956(86)90026-2

W. Baird and A. Bonato. Meyniel's conjecture on the cop number: a survey. J. Comb., 3(2):225-238, 2012.
https://doi.org/10.4310/JOC.2012.v3.n2.a6

B. Bollobás, G. Kun, and I. 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

A. Bonato, G. Hahn, and C. Wang. The cop density of a graph. Contrib. Discrete Math., 2(2):133-144, 2007.

N. Bowler, J. Erde, F. Lehner, and M. 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

E. Chiniforooshan. A better bound for the cop number of general graphs. J. Graph Theory, 58(1):45-48, 2008.
https://doi.org/10.1002/jgt.20291

N. E. Clarke, S. Fiorini, G. Joret, and D. O. Theis. A note on the cops and robber game on graphs embedded in non-orientable surfaces. Graphs Comb., 30(1):119-124, 2014.
https://doi.org/10.1007/s00373-012-1246-z

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

G. Gottlob, N. Leone, and F. Scarcello. Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. Journal of Computer and System Sciences, 66(4):775-808, 2003. Special Issue on PODS 2001.
https://doi.org/10.1016/S0022-0000(03)00030-8

W. B. Kinnersley. Cops and robbers is EXPTIME-complete. J. Combin. Theory Ser. B, 111:201-220, 2015.
https://doi.org/10.1016/j.jctb.2014.11.002

F. Lehner. On the cop number of toroidal graphs. J. Combin. Theory Ser. B, 151:250-262, 2021.
https://doi.org/10.1016/j.jctb.2021.06.008

L. Lu and X. Peng. On Meyniel's conjecture of the cop number. J. Graph Theory, 71(2):192-205, 2012.
https://doi.org/10.1002/jgt.20642

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

R. Nowakowski and P. Winkler. Vertex-to-vertex pursuit in a graph. Discrete Mathematics, 43(2):235-239, 1983.
https://doi.org/10.1016/0012-365X(83)90160-7

P. Prałat and N. Wormald. Meyniel's conjecture holds for random graphs. Random Structures Algorithms, 48(2):396-421, 2016.
https://doi.org/10.1002/rsa.20587

A. Quilliot. Jeux et pointes fixes sur les graphes. PhD thesis, Université de Paris VI, 1978.

A. Quilliot. A short note about pursuit games played on a graph with a given genus. Journal of Combinatorial Theory, Series B, 38(1):89-92, 1985.
https://doi.org/10.1016/0095-8956(85)90093-0

B. S. W. Schroeder. The copnumber of a graph is bounded by b 32 genus (G)c+3. In Categorical perspectives (Kent, OH, 1998), Trends Math., pages 243-263. Birkhäuser Boston, Boston, MA, 2001.
https://doi.org/10.1007/978-1-4612-1370-3_14

A. Scott and B. Sudakov. A bound for the cops and robbers problem. SIAM J. Discrete Math., 25(3):1438-1442, 2011.
https://doi.org/10.1137/100812963

P. Siriwong, R. Boonklurb, H. Liu, and S. Singhun. Cops and robber on cartesian products and some classes of hypergraphs. arXiv preprint arXiv:2107.11741, 2021.

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Joshua Erde, Mihyun Kang, Florian Lehner, Bojan Mohar, Dominik Schmid

PDF