Directed isoperimetry and infinitely fast robbers
math.CO
Submitted: 2026-10-28
Updated: 2026-10-28
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: We study the fast version of the cops and robber game on finite digraphs with unit-speed cops and an unbounded-speed robber.
Abstract
We study the fast version of the cops and robber game on finite digraphs with unit-speed cops and an unbounded-speed robber. We prove a lower bound for the cop number of every strongly connected digraph in terms of its order, maximum out-degree, and out-vertex expansion, extending Mehrabian's isoperimetric lower bound to digraphs, where connected components are replaced by forward reachable sets. For strongly connected abelian Cayley digraphs of fixed out-degree, we show that the ratio of the cop number to the number of vertices is comparable to each of out-vertex expansion, vertex expansion of the underlying undirected graph, minimum nontrivial character displacement, the square root of the unnormalized Laplacian spectral gap of the underlying undirected graph, and the reciprocal of its diameter. The comparison constants depend polynomially on the out-degree. In the undirected case, we also compare pathwidth with these parameters, complementing the bounded-degree treewidth comparison of Alon and Mehrabian. Combining the directed lower bound with recent cyclic sweep techniques for abelian Cayley graphs, we determine the order of the cop number of positively oriented tori and directed Heisenberg graphs.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality