Conjecture on the cop number of fast robbers on grids

For RNR\in\mathbb{N}, let fR(n)f_R(n) be the minimum number of cops needed to catch a robber of speed RR on an n×nn\times n grid, where the cops move at unit speed. Here “sufficiently large” refers to the robber speed parameter RR.

Fast-robber grid conjecture. For all sufficiently large RNR\in\mathbb{N},

fR(n)=n1o(1)as n.f_R(n)=n^{1-o(1)}\quad\text{as }n\to\infty.

The conjecture says that, for sufficiently large fixed robber speeds, the trivial upper bound fR(n)nf_R(n)\le n is asymptotically close to the truth. The paper proves a much weaker exponential lower bound for one sufficiently large speed and leaves this near-linear behaviour conjectural.

Sources & referencesView supporting material

Primary source

Paul Balister, Béla Bollobás, Bhargav Narayanan and Amy Shaw, “Catching a fast robber on the grid”, arXiv:1609.01002 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.