To Catch a Falling Robber
William B. Kinnersley\thanks{Department of Mathematics
Ryerson University Toronto
ON
Canada
M5B 2K3
wkinners@ryerson.ca.
We consider a Cops-and-Robber game played on the subsets of an $n$-set. The robber starts at the full set; the cops start at the empty set. On each turn, the robber moves down one level by discarding an element, and each cop moves up one level by gaining an element. The question is how many cops are needed to ensure catching the robber when the robber reaches the middle level. A.~Hill posed the problem and provided a lower bound of $2^{n/2$ for even $n$ and $\CH{n{\CL{n/22^{-\FL{n/2$ for odd $n$. We prove an upper bound that is within a factor of $O(\ln n)$ times this lower bound.\\ Keywords: Cops-and-robber game; cop number; hypercube; $n$-dimensional cube
1406.2228.tex
\documentclass[12pt]{article}
\usepackage{amsmath,amsthm,amssymb,fullpage}

\newcommand{\size}[1]{\left \vert #1 \right \vert}
\newcommand{\ceil}[1]{\left \lceil #1 \right \rceil}
\newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor}
\newcommand{\cart}{\, \Box \,}
\newcommand{\prob}[1]{\mathbb{P} \left [\, #1 \, \right ]}
\newcommand{\expect}[1]{\mathbb{E} \left [\, #1 \, \right ]}
\newcommand{\eps}{\varepsilon}
\newcommand{\cnum}[1]{c(#1)}  % copnumber; Hill used "C"

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{obs}[theorem]{Observation}
\newtheorem{cor}[theorem]{Corollary}

\def\nul{\varnothing} %{\emptyset}
\def\st{\colon\,}   %"such that"
\def\VEC#1#2#3{#1_{#2},\ldots,#1_{#3}}
\def\VECOP#1#2#3#4{#1_{#2}#4\cdots #4 #1_{#3}}
\def\SE#1#2#3{\sum_{#1=#2}^{#3}}  \def\SGE#1#2{\sum_{#1\ge#2}}
\def\PE#1#2#3{\prod_{#1=#2}^{#3}} \def\PGE#1#2{\prod_{#1\ge#2}}
\def\UE#1#2#3{\bigcup_{#1=#2}^{#3}}
\def\IE#1#2#3{\bigcap_{#1=#2}^{#3}}
\def\CH#1#2{\binom{#1}{#2}}
\def\FR#1#2{\frac{#1}{#2}}
\def\FL#1{\left\lfloor{#1}\right\rfloor} \def\FFR#1#2{\FL{\frac{#1}{#2}}}
\def\CL#1{\left\lceil{#1}\right\rceil}   \def\CFR#1#2{\CL{\frac{#1}{#2}}}
\def\esub{subseteq}
\def\kfrac{\FR k{n-k+1}}
\def\cS{{\mathcal S}}




\begin{document}

\title{To Catch a Falling Robber}

\author{
William B. Kinnersley\thanks{Department of Mathematics, Ryerson University
Toronto, ON, Canada, M5B 2K3, wkinners@ryerson.ca.}\, and 
Douglas B. West\thanks{Departments of Mathematics, Zhejiang Normal University,
Jinhua, China 321004,
and  University of Illinois, Urbana, IL 61801, west@math.uiuc.edu.
Research supported by Recruitment Program of Foreign Experts,
1000 Talent Plan, State Administration of Foreign Experts Affairs, China.}
}

\date{}
\maketitle


\begin{abstract}
We consider a Cops-and-Robber game played on the subsets of an $n$-set.
The robber starts at the full set; the cops start at the empty set.
On each turn, the robber moves down one level by discarding an element,
and each cop moves up one level by gaining an element.  The question is
how many cops are needed to ensure catching the robber when the robber
reaches the middle level.  A.~Hill posed the problem and provided a lower
bound of $2^{n/2}$ for even $n$ and $\CH{n}{\CL{n/2}}2^{-\FL{n/2}}$ for odd $n$.
We prove an upper bound that is within a factor of $O(\ln n)$ times this 
lower bound.\\
Keywords: Cops-and-robber game; cop number; hypercube; $n$-dimensional cube
\end{abstract}

\baselineskip=16pt

\section{Introduction}
The game of {\it Cops-and-Robber} is a pursuit game on a graph.
In the classical form, there is one robber and some number of cops.
The players begin by occupying vertices, first the cops and then the robber.
In each subsequent round, each cop and then the robber can move along an
edge to an adjacent vertex.  The cops win if at some point there is a cop
occupying the same vertex as the robber.  The {\it cop number} of a graph $G$,
written $c(G)$, is the least number of cops that can guarantee winning.

The game of Cops-and-Robber was independently introduced by
Quilliot~\cite{Qui78} and by Nowakowski and Winkler~\cite{NW83}; both
papers characterized the graphs with cop number $1$.  The cop number as 
a graph invariant was then introduced by Aigner and Fromme~\cite{AF84}.
Analysis of the cop number is the central problem in the study of the game
and often is quite challenging.  The foremost open problem in the field is
Meyniel's conjecture that $c(G) = O(\sqrt{n})$ for every $n$-vertex connected
graph $G$ (first published in~\cite{F}).  For more background on
Cops-and-Robber, see~\cite{BN11}.

We consider a variant of the Cops-and-Robber game on a hypercube, introduced in
the thesis of A.~Hill~\cite{Hil08}.  This variant restricts the initial
positions and the allowed moves.  The $n$-dimensional hypercube is the graph
with vertex set $\{0,1\}^n$ (the set of binary $n$-tuples) in which vertices
are adjacent if and only if they differ in one coordinate.  View the vertices
as subsets of $\{1,\ldots,n\}$, and let the {\it $k$th level} consist of the
vertices whose size as subsets if $k$.

The robber starts at the full set $\{1,\ldots,n\}$; the cops start at the
empty set $\nul$.  On the $k$th round, the cops all move from level $k-1$ to
level $k$, and then the robber moves from level $n+1-k$ to level $n-k$.
If the cops catch the robber, then they do so on round $\CL{n/2}$ at level
$\CL{n/2}$, when they move if $n$ is odd, and by the robber moving onto them if
$n$ is even.

Let $c_n$ denote the minimum number of cops that can guarantee winning the
game.  Hill~\cite{Hil08} provided the lower bound $2^{n/2}$ for even $n$ and
$\CH{n}{\CL{n/2}}$ for odd $n$.  Note that in this variant the cops have in
some sense only one chance to catch the robber, on the middle level.  When
the cops have the opportunity to chase the robber by moving both up and down,
it is known that the value is much smaller, with the cop number of the 
$n$-dimensional hypercube graph being $\CL{(n+1)/2}~\cite{MM87}$.

We first include a proof of Hill's lower bound, since its ideas motivate our
arguments.  We then prove our main result: an upper bound that is within a
factor of $O(\ln n)$ times this lower bound.

\bigskip 

\begin{theorem}[\cite{Hil08}]\label{lower}
$c_n \ge 
\left \{ \begin{array}{ll}
   2^{m},                   &n=2m;\\
   2^{-m}\binom{2m+1}{m+1}, &n=2m+1.                
\end{array} \right.$
\end{theorem}
\begin{proof}
After each move by the robber, some cops may no longer lie below the robber.
Such cops are effectively eliminated from the game.  We call them {\em evaded
cops}; cops not yet evaded are {\em surviving cops}.  

Consider the robber strategy that greedily evades as many cops as possible with
each move.  Deleting an element from the set at the robber's current position
evades all cops whose set contains that element.  On the $k$th round, the
surviving cops sit at sets of size $k$, and the robber has $n-k+1$ choices of
an element to delete.  Since each surviving cop can be evaded in $k$ ways,
the fraction of the surviving cops that the robber can evade on this move is
at least $\FR k{n-k+1}$.

After the first $m$ rounds, where $m=\FL{n/2}$, the fraction of the cops that
survive is at most $\prod_{i=1}^{m} \left ( 1 - \frac{i}{n-i+1} \right )$. 
When $n=2m$, we compute
$$
\PE i1m \left(1-\frac{i}{2m-i+1}\right)
= \PE i1m \frac{2m-2i+1}{2m-i+1}
= \frac{(2m)!}{(2m)!\cdot2^m} = 2^{-m}.
$$
When $n=2m+1$, we compute
$$
\prod_{i=1}^{m} \left(1-\frac{i}{2m-i+2} \right)
= \prod_{i=1}^{m} \frac{2m-2i+2}{2m-i+2}
= \frac{2^m m! (m+1)!}{(2m+1)!}
= 2^m \Big/ \binom{2m+1}{m+1}.%  \sim 2^{-(m+1)}\sqrt{m\pi}.
$$
In either case, with fewer than the number of cops specified, the number of
cops surviving to catch the robber after $m$ moves by the robber is less than
$1$, and the robber wins.
\end{proof}

\section{The Upper Bound}

If there are enough cops to cover the entire middle level, then the robber
cannot sneak through.  The size of the middle level is asymptotic to 
$2^n/\sqrt{\pi n/2}$.  This trivial upper bound is roughly the square of the
lower bound above.  When n is odd one can reduce the upper bound slightly by
observing that one only needs to reach a subset of level $(n-1)/2$ that hits
the neighborhoods of all the sets at level $(n+1)/2$.  However, as the robber
starts to move, the family of sets that need to be protected shrinks.

Our upper bound on $c_n$ is within a factor of $O(\ln n)$ of the lower bound in
Theorem~\ref{lower}.

\bigskip 

\begin{theorem}\label{upper}
$c_n \le
\left \{ \begin{array}{ll}
   O(2^{m}\ln n ),                   &n=2m;\\
   O(2^{-m}\binom{2m+1}{m+1}\ln n ), &n=2m+1.                
\end{array} \right.$
\end{theorem}
\begin{proof}
We again use the terminology of evaded and surviving cops.  The cops win if
some cop survives through $m$ rounds.  We consider the case $n=2m$ first,
returning later to the case $n=2m+1$.

Initially, some number $C$ of cops begin at $\nul$.  Let $R$ be the current
set occupied by the robber.  On his $k$th turn, for $k\le m-7$, each surviving
cop at set $S$ chooses the next element for his set uniformly at random from
among $R-S$.  For their last seven turns, the cops use a slightly different
strategy, which we explain later.  We claim that for any strategy used by
the robber, this cop strategy succeeds with positive probability when
$C=(c\ln n)2^{m}$, for some constant $c$ to be specified later.  That is,
some outcome of random choices in the cop strategy in response to the robber
strategy catches the robber.

We argued in Theorem~\ref{lower} that the robber can evade the fraction
$\FR k{n-k+1}$ of the surviving cops in round $k$.  We aim to show that the
robber cannot do much better than this against the random strategy for the cops.
Let $B_k$ be the event that the robber can, by deleting an appropriate element
of his current set $R$, evade more than the fraction $(1+\eps_k)\kfrac$ of the
surviving cops on his $k$th move, where $\eps_k = 1/k^3$.  We claim that, with
positive probability, all the events $\VEC B1{m-7}$ fail to occur.

Suppose that the robber deletes element $i$ on round $k$.  The probability that
a given surviving cop at level $k$ sits at a set $S$ containing $i$ is the
probability that it added $i$ to $S$ sometime during the first $k$ rounds.  A
surviving cop sits at a set contained in $R$, and the robber has made no 
distinction among the elements of $R$.  Also, given $S\esub R$, the $k$-lists
of elements from $R$ are equally likely to have been the list of elements added
to $S$ by the cop.  Since $k$ of the elements have been selected by the cop
from the $(n-k+1)$-set $R$, the probability that any one of them was added is
exactly $\kfrac$.

Hence the probability that a given surviving cop will be evaded when the
robber deletes $i$ is $\kfrac$.  Letting $X_{k,i}$ be the number of surviving
cops in round $k$ who are evaded when the robber deletes $i$, we have
$\expect{X_{k,i}}=N_k\cdot\kfrac$, where $N_k$ is the number of surviving cops
at level $k$.  We need the probability that $X_{k,i}$ does not differ much from
its expectation.  Let $p = \kfrac$ and $\mu = N_kp$.  By the Union Bound,
$$\prob{B_k} \le \sum_i \prob{X_{k,i} > (1+\eps_k)\mu} = (n-k+1)\prob{X > (1+\eps_k)\mu},$$
where $X \sim \mathrm{Bin}(N_k, p)$.  The Chernoff Bound now yields
\begin{equation}
\prob{B_k} \le 2(n-k+1)e^{-\eps_k^2\mu/3}.
\end{equation}

Note that $\mu$ decreases as $N_k$ decreases, so we obtain an upper bound on
$\prob{B_k}$ by substituting for $N_k$ a lower bound on $N_k$.  For $k \le m-7$,
if all of $\VEC B1{k-1}$ fail to occur, then
\begin{equation}
N_k\ge C\cdot\PE i1{k-1} \left(1-(1+\eps_i)\frac{i}{n-i+1} \right).
\end{equation}
Since the factors are less than $1$, the lower bound on $N_k$ decreases as
$k$ increases.  To facilitate comparison of this product to the product in
Theorem~\ref{lower}, we compute
\begin{align*}
\PE i1m \frac{1 - \frac{i}{n-i+1}}{1 - (1+\eps_i)\frac{i}{n-i+1}} 
          &= \PE i1m \frac{n-2i+1}{n-2i+1-i\eps_i}
           = \PE i1m \left ( 1 + \frac{i\eps_i}{n-2i+1-i\eps_i} \right )\\
          &= \PE i1m \left ( 1 + \frac{1/i^2}{n-2i+1-1/i^2} \right )
         \le \PE i1m \left ( 1 + \frac{1}{i^2} \right )
         \le \prod_{i=1}^{\infty} \left ( 1 + \frac{1}{i^2} \right ).
\end{align*}
Note that $1+\FR{1/i^2}{n-2i+1-1/i^2}>1+1/i^2$ when $i=m=n/2$; if $m\ge2$,
then this factor can be combined with another to get the inequality in the
right direction.
The final product converges to some value $P$.  (The convergence of the product
can be shown by taking the logarithm and using the Integral Test to verify the
convergence of the resulting sum; the details are routine but mildly tedious.)
Thus
$$\prod_{i=1}^{m} \left ( 1 - (1+\eps_i)\frac{i}{n-i+1} \right ) \ge \frac{1}{P} \prod_{i=1}^{m} \left ( 1 - \frac{i}{n-i+1} \right ) = \frac{1}{P}2^{-m}.$$
For $k \le m-7$, the lower bound in (2) has at most $m-8$ factors.  Comparing
it to the full product, we obtain
\begin{align*}
N_k &\ge C \cdot \PE i1{m-8} \left ( 1 - (1+\eps_i)\frac{i}{n-i+1} \right )
 = C\cdot\FR{\PE i1m \left(1-(1+\eps_i)\frac{i}{n-i+1} \right )}
         {\PE i{m-7}m\left(1-(1+\eps_i)\frac{i}{n-i+1} \right )}\\
  &\ge C\cdot\FR{\FR1P 2^{-m}}{\PE i{m-7}m \left(1-\frac{i}{n-i+1}\right)}
   = \frac{C}{P} 2^{-m} \frac{(m+8)(m+7)\cdots(m+1)}{(15)(13) \cdots (3)(1)}\\
    &\ge \frac{C}{P} 2^{-m} \frac{n^8}{5.2 \cdot 10^8} 
      = \frac{c}{P \cdot 5.2 \cdot 10^8}n^8 \ln n. 
\end{align*}
By (1),
$$
\prob{B_k} \le 2(n-k+1)e^{-\FR1{3k^6}\kfrac\FR c{P\cdot5.2\cdot10^8}n^8\ln n}
\le 2ne^{-\frac{c}{3P \cdot 5.2 \cdot 10^8}n^2 \ln n}.
$$
By the Union Bound,
$$
\prob{\UE k1{m-7} B_k} \le n(n-14)n^{-\frac{c}{3P \cdot 5.2 \cdot 10^8}n^2}.
$$
The bound tends to $0$ as $n$ tends to infinity, so almost always none of
$\VEC B1{m-7}$ occur.

Now consider the state of the game just before the cops move to level $m-6$.
Let $N$ be the number of surviving cops.  Assuming that no $B_k$ has occurred, 
the argument above (with a few small changes) shows that $N$ is at least
$\frac{c}{P \cdot 1.8 \cdot 10^7}n^7 \ln n$; denote this lower bound by $N^*$.
The cops now adopt a different strategy.  Let $\cS$ denote the family of sets
at level $m$ that remain under the robber.  Each surviving cop chooses a path
to some point in $\cS$ that it can reach, uniformly at random, and follows this
path for the remainder of the game regardless of the robber's moves.
We have argued earlier that at any level, each surviving cop is equally likely
to sit at any set under the robber.  Since this is true at level $m-7$,
and each set in $\cS$ is reached by the same number of paths from level $m-7$,
each cop that survives to level $m-7$ is equally likely to reach any vertex
of $\cS$ (not conditioned on its location on level $m-7$; conditioned only
on it surviving to level $m-7$).

If each point in $\cS$ is reached by at least one cop, then the cops win, since
the robber then cannot reach any point at level $m$ without being caught.  For
$A \in \cS$, let $X_A$ denote the event that no cop reaches $A$.  We have argued
that each of the $N$ cops surviving to level $m-7$ will by level $m$ have
traversed a chain from $\nul$ to $\cS$, with all such chains being equally
likely.  We have $\size{\cS} = \binom{m+7}{7}<(\FR{ne}{14})^7$ for sufficiently
large $n$.  Letting $b=(14/e)^7$,
$$
\prob{X_A} \le \left (1 - \frac{b}{n^7}\right )^{N^*}
\le e^{-\frac{b}{n^7}N^*} \le e^{-\frac{c}{30P} \ln n}.
$$
Now the Union Bound yields
$$
\prob{\bigcup_{A \in \cS} X_A} \le \frac{n^7}{b}e^{-\frac{c}{30P} \ln n}
= \frac{n^7}{b}n^{-\frac{c}{30P}}.
$$

If none of the events $B_k$ and $X_A$ occur, then the cops win.  But
$$
\prob{\left(\UE k1{m-7} B_k \right)\cup\left(\bigcup_{A \in \cS} X_A \right)}
\le n^2 e^{-\frac{c}{3P \cdot 5.2 \cdot 10^8}n \ln n}
+ \frac{n^7}{b}n^{-\frac{c}{30P}}.
$$
Taking $c=210P$, this probability tends to $1/b$ as $n$ tends to infinity.
Hence the cops win with positive probability, which completes the proof for
$n = 2m$.

When $n=2m+1$, the cops use the same strategy until their final move (from level
$m$ to $m+1$).  We claim that this strategy succeeds with positive probability
when $C = c \ln n 2^{(m+1)}/\sqrt{n}$ for some constant $c$.  This is
equivalent to the claimed bound, since
$\binom{2m+1}{m+1} \sim 2^{2m+1} / \sqrt{m\pi}$.  As before,
$\prob{\bigcup_{k=1}^{m-7} B_k}$ tends to 0 as $n$ tends to infinity.  Let $N$
denote the number of surviving cops just before round $m-6$; arguments like
those used above yield $N \ge N^*$, where $N^*=\FR{cn^7}{P\cdot8.3\cdot10^7}$.  

Consider the state of the game just before round $m-6$.  Let $\cS$ and $\cS'$
denote the families of sets at levels $m$ and $m+1$, respectively, still below
the robber.  As before, each cop now follows a uniformly randomly chosen path
to $\cS$.  After the robber's $m$th move, the cops sit at sets in $\cS$, and the
robber sits somewhere in $\cS'$.  If some cop still remains below the robber,
then that cop captures the robber and the cops win; otherwise, the robber wins.
Hence it suffices to ensure that, for each $A \in \cS'$, some cop reaches a
set below $A$ in $\cS$.  

Since $\size{\cS'} = \binom{m+8}{7}$ and $\size{\cS} = \binom{m+8}{8}$, we have
$\size{\cS'} \le n^7/b$ and $\size{\cS} \le n^8/b'$ for sufficiently large $n$,
where $b'=(16/e)^8$.  For $A \in \cS'$, let $X_A$ denote the event that no cop
reaches a set below $A$.  For each surviving cop, the chains from $\nul$ to
$\cS$ are equally likely to be followed during the game.  Since $A$ has $m+1$
neighbors in $\cS$, a given cop reaches some set below $A$ with probability at
least $\frac{m+1}{n^8/b'}$, which is at least $\frac{b'/2}{n^7}$.  Thus
$$
\prob{X_A} \le \left (1 - \frac{b'/2}{n^7}\right )^{N^*} \le
e^{-\frac{b'/2}{n^7}N^*} \le e^{-\frac{3c}{5P} \ln n}.
$$
By the Union Bound,
$$
\prob{\bigcup_{A \in \cS'} X_A} \le \frac{n^7}{b}e^{-\frac{3c}{5P} \ln n} =
\frac{n^7}{b}n^{-\frac{3c}{5P}}.
$$
Taking $c = 35P/3$, the claim follows as before.
\end{proof}

By more careful analysis, one can allow the cops to change strategies at level
$m-5$ instead of level $m-7$.  This does not affect the asymptotics of the
bound, but it does yield some improvement in the leading constant.

\begin{thebibliography}{99}

{\small
\bibitem{AF84} M. Aigner and M. Fromme, A game of cops and robbers,
{\em Discrete Applied Mathematics} 8 (1984), 1--12.

\bibitem{BN11} A. Bonato and R.J. Nowakowski, {\em The Game of Cops
and Robbers on Graphs}, American Mathematical Society, Providence,
Rhode Island, 2011.

\bibitem{F}
P. Frankl, Cops and robbers in graphs with large girth and Cayley
graphs, {\em Discrete Applied Mathematics} 17 (1987), 301--305.

\bibitem{Hil08}
A. Hill, 
Cops and Robbers: Theme and Variations, 
PhD Thesis.  {\it ProQuest Dissertations and Theses}, 2008.

\bibitem{MM87} M. Maamoun and H. Meyniel, On a game of policemen and
robber, {\em Discrete Applied Mathematics} 17 (1987), 307--309.

\bibitem{NW83} R.J. Nowakowski and P. Winkler, Vertex-to-vertex
pursuit in a graph, {\em Discrete Mathematics} 43 (1983) 235--239.

\bibitem{Qui78} A. Quilliot, Jeux et pointes fixes sur les graphes,
Th\`ese de 3\`eme cycle, Universit\'e de Paris VI, 1978, 131--145.

}

\end{thebibliography}
\end{document}

1406.2228.extracted_bib
{AF84 M. Aigner and M. Fromme, A game of cops and robbers, {\em Discrete Applied Mathematics 8 (1984), 1--12.
1406.2228.extracted_bib
{BN11 A. Bonato and R.J. Nowakowski, {\em The Game of Cops and Robbers on Graphs, American Mathematical Society, Providence, Rhode Island, 2011.
1406.2228.extracted_bib
{F P. Frankl, Cops and robbers in graphs with large girth and Cayley graphs, {\em Discrete Applied Mathematics 17 (1987), 301--305.
1406.2228.extracted_bib
{Hil08 A. Hill, Cops and Robbers: Theme and Variations, PhD Thesis. {ProQuest Dissertations and Theses, 2008.
1406.2228.extracted_bib
{MM87 M. Maamoun and H. Meyniel, On a game of policemen and robber, {\em Discrete Applied Mathematics 17 (1987), 307--309.
1406.2228.extracted_bib
{NW83 R.J. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, {\em Discrete Mathematics 43 (1983) 235--239.
1406.2228.extracted_bib
{Qui78 A. Quilliot, Jeux et pointes fixes sur les graphes, Th\`ese de 3\`eme cycle, Universit\'e de Paris VI, 1978, 131--145.