The Capture Time of the Hypercube

  • Anthony Bonato
  • Przemysław Gordinowicz
  • Bill Kinnersley
  • Paweł Prałat
Keywords: Cops and Robbers, hypercube, coupon-collector problem

Abstract

In the game of Cops and Robbers, the capture time of a graph is the minimum number of moves needed by the cops to capture the robber, assuming optimal play. We prove that the capture time of the $n$-dimensional hypercube is $\Theta (n\ln n)$. Our methods include a novel randomized strategy for the players, which involves the analysis of the coupon-collector problem.

Published
2013-04-30
Article Number
P24