On Meyniel's Conjecture in Random Hypergraphs

The game of \emph{Cops and Robbers} is a two player pursuit game on graphs where a team of cops attempts to catch a robber.

The cop number $c(G)$ of a graph $G$ is the minimum number of cops needed to guarantee a winning strategy in $G$.

A famous conjecture of Meyniel says that if $G$ is connected, then $c(G)=O(\sqrt{n})$.

Erde, Kang, Lehner, Mohar and Schmid considered its generalization to $k$-uniform hypergraphs and conjectured that the cop number of such hypergraphs is $O(\sqrt{n/k})$.

This may be understood as a hypergraph version of Meyniel's conjecture.

In this paper we prove this conjecture for a class of \textit{expanding} hypergraphs and show that with high probability the conjecture holds for random hypergraphs $H^k(n,p))$ provided $k\geq \log^3n$ and the typical degree, $p\binom{n-1}{k-1}$, is $\omega(\log^3n)$.