Directed isoperimetry and infinitely fast robbers

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.

Fast robbers on abelian Cayley graphs and digraphs
Arindam Biswas
arXiv3 Sep 2026PreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
Improved bounds for the lazy cops and robbers on generalized hypercubes
Anand Babu, Ashwin Jacob, Karunakaran Murali Krishnan +2
arXiv4 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Cops and Robbers on Graphs without Long or Short Holes
Alexander Clow
arXiv26 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Isoperimetry of singular CMC hypersurfaces
Kobe Marshall-Stevens, Gongping Niu
arXiv9 Oct 2026PreprintCC BY 4.0Full textGeometry & topologyarXiv
Anchored isoperimetry in percolation
Sahar Diskin, Lyuben Lichev, Ritvik Ramanan Radhakrishnan +2
arXiv28 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics ProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{biswas2026directed,
  title = {{Directed isoperimetry and infinitely fast robbers}},
  author = {Arindam Biswas},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.38552},
  eprint = {2610.38552},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38552},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Directed isoperimetry and infinitely fast robbers
AU  - Arindam Biswas
PY  - 2026
DA  - 2026/10/28
PB  - arXiv
DO  - 10.48550/arxiv.2610.38552
UR  - https://arxiv.org/abs/2610.38552
AB  - 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.
ER  -

Abstract

Related

Cite