Catching a fast robber on the grid

Paul Balister; Amy Shaw; Béla Bollobás; Bhargav Narayanan

doi:10.1016/j.jcta.2017.06.009

Catching a fast robber on the grid

Paul Balister, Amy Shaw, Béla Bollobás, Bhargav Narayanan

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

We study the problem of cops and robbers on the grid where the robber is allowed to move faster than the cops. It is well known that two cops are necessary and sufficient to catch the robber on any finite grid when the robber has unit speed. Here, we prove that if the speed of the robber exceeds a sufficiently large absolute constant, then the number of cops needed to catch the robber on an n×n grid is exp⁡(Ω(log⁡n/log⁡log⁡n)).

Original language	English (US)
Pages (from-to)	341-352
Number of pages	12
Journal	Journal of Combinatorial Theory. Series A
Volume	152
DOIs	https://doi.org/10.1016/j.jcta.2017.06.009
State	Published - Nov 2017
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Cops and robbers
Games on graphs

Access to Document

10.1016/j.jcta.2017.06.009

Cite this

@article{da86ad0995654fee8530a9adb152d896,

title = "Catching a fast robber on the grid",

abstract = "We study the problem of cops and robbers on the grid where the robber is allowed to move faster than the cops. It is well known that two cops are necessary and sufficient to catch the robber on any finite grid when the robber has unit speed. Here, we prove that if the speed of the robber exceeds a sufficiently large absolute constant, then the number of cops needed to catch the robber on an n×n grid is exp⁡(Ω(log⁡n/log⁡log⁡n)).",

keywords = "Cops and robbers, Games on graphs",

author = "Paul Balister and Amy Shaw and B{\'e}la Bollob{\'a}s and Bhargav Narayanan",

note = "Funding Information: The first and second authors were partially supported by National Science Foundation grant DMS-1301614 and the second author also wishes to acknowledge support from EU MULTIPLEX grant 317532 . Publisher Copyright: {\textcopyright} 2017 Elsevier Inc.",

year = "2017",

month = nov,

doi = "10.1016/j.jcta.2017.06.009",

language = "English (US)",

volume = "152",

pages = "341--352",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Catching a fast robber on the grid

AU - Balister, Paul

AU - Shaw, Amy

AU - Bollobás, Béla

AU - Narayanan, Bhargav

N1 - Funding Information: The first and second authors were partially supported by National Science Foundation grant DMS-1301614 and the second author also wishes to acknowledge support from EU MULTIPLEX grant 317532 . Publisher Copyright: © 2017 Elsevier Inc.

PY - 2017/11

Y1 - 2017/11

N2 - We study the problem of cops and robbers on the grid where the robber is allowed to move faster than the cops. It is well known that two cops are necessary and sufficient to catch the robber on any finite grid when the robber has unit speed. Here, we prove that if the speed of the robber exceeds a sufficiently large absolute constant, then the number of cops needed to catch the robber on an n×n grid is exp⁡(Ω(log⁡n/log⁡log⁡n)).

AB - We study the problem of cops and robbers on the grid where the robber is allowed to move faster than the cops. It is well known that two cops are necessary and sufficient to catch the robber on any finite grid when the robber has unit speed. Here, we prove that if the speed of the robber exceeds a sufficiently large absolute constant, then the number of cops needed to catch the robber on an n×n grid is exp⁡(Ω(log⁡n/log⁡log⁡n)).

KW - Cops and robbers

KW - Games on graphs

UR - http://www.scopus.com/inward/record.url?scp=85030463696&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85030463696&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2017.06.009

DO - 10.1016/j.jcta.2017.06.009

M3 - Article

AN - SCOPUS:85030463696

SN - 0097-3165

VL - 152

SP - 341

EP - 352

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

ER -

Catching a fast robber on the grid

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this