The capture time of the hypercube (Q1953506): Difference between revisions

Summary: 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.