Cop number √(n/k) bound for k-uniform hypergraphs

Conjecture 1.4 · arXiv:2307.15512

arXiv Conjecture high confidence— first stated 2024-04-11

Authors: Joshua Erde, Mihyun Kang, Florian Lehner, Bojan Mohar, Dominik Schmid

Status open high confidence

No follow-up paper proving or disproving Conjecture 1.4 was found. The source paper itself (arXiv:2307.15512, published in Canadian Journal of Mathematics 2025) provides the best-known upper bound of O(sqrt(n/k) log n) for the cop number of the random k-uniform hypergraph G^k(n,p), falling short of the conjectured O(sqrt(n/k)) by a logarithmic factor. The conjecture remains open as a hypergraph analogue of Meyniel's conjecture.

Reviewer notes. The EUROCOMB 2023 proceedings paper (journals.phil.muni.cz/eurocomb/article/view/35592) is the conference version of the same paper, not a follow-up. The journal version appeared in Canadian Journal of Mathematics Vol. 77 Issue 4 (August 2025). No independent follow-up addressing the full conjecture was found in three targeted web searches.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $H$ be a connected $k$-graph on $n$ vertices. Then $c(H) = O\!\left(\sqrt{\dfrac{n}{k}}\right)$.

Context

The authors introduce this as a generalisation of Meyniel's conjecture to $k$-uniform hypergraphs, motivated by a blow-up construction that shows $c(H) = \Omega\!\left(\sqrt{n/k}\right)$ is achievable. They further observe that for any polynomial $k = n^\alpha$ with $\alpha < 1$, Conjecture 1.4 implies Meyniel's conjecture.

Notes. PDF source — LaTeX reconstructed from abstract statement and the formal conjecture environment; statement is unambiguous from context.

Source paper

Catching a robber on a random $k$-uniform hypergraph
Joshua Erde, Mihyun Kang, Florian Lehner, Bojan Mohar, Dominik Schmid · 2024-04-11
https://arxiv.org/abs/2307.15512 PDF source