Metraipolis › archive › dc_b9ef91d23edc

Directed isoperimetry and infinitely fast robbers — arXiv:2610.38552

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.38552
License (as archived)
CC0-1.0
Archived
2026-11-01T02:37:43.722Z
SHA-256 of the archived text
42fe697ac55c753d22fcb9b52ac7d5f153a278d0feb9e0f1db9a4a6559c67890
Stable URL of this page
https://metraipolis.com/documento/dc_b9ef91d23edc

How to cite

Directed isoperimetry and infinitely fast robbers — arXiv:2610.38552 — arXiv (en), https://arxiv.org/abs/2610.38552 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b9ef91d23edc (Metraipolis archive dc_b9ef91d23edc, sha256 42fe697ac55c753d22fcb9b52ac7d5f153a278d0feb9e0f1db9a4a6559c67890)
BibTeX
@misc{dcb9ef91d23edc,
  title = {Directed isoperimetry and infinitely fast robbers — arXiv:2610.38552},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.38552},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b9ef91d23edc; sha256 42fe697ac55c753d22fcb9b52ac7d5f153a278d0feb9e0f1db9a4a6559c67890},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38552. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.38552 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:15:28.253Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).