%add outline
\documentclass{beamer}
\mode<presentation>
{
  \usetheme{Warsaw}
  % or ...

  \setbeamercovered{transparent}
  % or whatever (possibly just delete it)
}


\usepackage[english]{babel}
% or whatever

\usepackage[latin1]{inputenc}
% or whatever

\usepackage{tikz}
\usepackage{multirow}
\usepackage{amsmath}
\usetikzlibrary{decorations.pathmorphing}

\usepackage[T1]{fontenc}
\usepackage{concrete}

% Or whatever. Note that the encoding and the font should match. If T1
% does not look nice, try deleting the line with the fontenc.


\title[Cops and Robber Game]{The Cops and Robber Game \\with a Fast Robber}
\newcommand{\poly}{\operatorname{poly}}

\author[Abbas]
{Abbas~Mehrabian\\{\small \texttt{amehrabi@uwaterloo.ca}}}

\institute{University of Waterloo}

\date
{March 4th, 2011}

\subject{Talks}

% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

% \pgfdeclareimage[height=0.5cm]{university-logo}{codept}
% \logo{\pgfuseimage{university-logo}}

\tikzstyle{graphnode}=[circle, draw, fill=black!100,
                        inner sep=0pt, minimum width=4pt]
%\tikzstyle{unmatched}=[graphnode,fill=black!0]
%\tikzstyle{matched}=[graphnode,fill=black!100]
\tikzstyle{robber}=[graphnode,red!100, fill=red!100]
\tikzstyle{cop}=[graphnode,blue!100, fill=blue!100]
%\tikzstyle{matching} = [ultra thick]

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{Outline}
  \tableofcontents
\end{frame}

\section{Introduction}

\subsection{Game definition}

\begin{frame}{Game Definition}
\begin{definition}[The Game of Cops and Robber]
{\begin{itemize}
\item \small Let $G$ be a graph and $s$ be a positive integer.
\item \small  There is a set of \alert{cops} and a \alert{robber}.
\item  \small In the beginning,
\begin{itemize}
\item  \small First, each cop chooses a starting vertex.
\item  \small Then, the robber chooses a starting vertex.
\end{itemize}
\item  \small In each round,
\begin{itemize}
\item  \small First, each cop chooses to stay or go to an adjacent vertex.
\item  \small Then, the robber chooses to stay, or move along a cop-free path of length $\leq s$.
\end{itemize}
\item  \small The cops \alert{capture} the robber if, at some moment, a cop is at the same vertex with the robber.
\end{itemize}}
\end{definition}
Think of $s$ as the \alert{speed} of the robber.
\end{frame}

\begin{frame}{Some Remarks/Assumptions About the Game}
\begin{enumerate}
\item This is a perfect-information game: the players see each other.
\item More than one cops can be at the same vertex.
\item The robber cannot jump over a cop.
\item The moves are deterministic (no randomness).
\item When describing a strategy for the cops,
we assume the robber is clever; and vice versa.
\end{enumerate}
\end{frame}

\begin{frame}{Cop Number}
\begin{definition}
The minimum number of cops that are needed to capture \\ the (clever) robber is denoted by \alert{$c_s(G)$}.
\end{definition}
\begin{example}
\begin{itemize}
\item For every $s$, if $G$ is the complete graph, then $c_s(G) = 1$.
\item For every $s$, if $G$ is a path, then $c_s(G) = 1$.
\item For every $s$, if $G$ is a cycle with $>3$ vertices, then $c_s(G) = 2$.
\item If $G$ is the $4\times 8$ grid, then $c_1(G) = 2$.
\item If $G$ is the $4\times 4$ grid, then $c_3(G) > 2$.
\item If $G$ is the $m\times m$ grid, then $c_{2m}(G) = m$.
\end{itemize}
\end{example}
\end{frame}

\subsection{Known results}

\begin{frame}{Some Known Results}{for $s=1$}
\begin{itemize}
\item The game was defined independently by Quilliot'78 and Nowakowski and Winkler'83.
\item If $G$ is planar, then $c_1(G) \leq 3$. \hfill [Aigner and Fromme'84]
\item If $G$ is chordal, then $c_1(G) = 1$. \hfill [Quilliot'86]
\item If $G$ has no cycle with less than $g$ vertices, then $c_1(G) > (\delta - 1) ^ {g/8}$. \hfill [Frankl'87]
\item If $G$ is a $d$-dimensional grid, \\ then $c_1(G) = \lceil \frac{d+1}{2} \rceil$. \hfill [Neufeld and Nowakowski'98]
\item If $G$ has no cycle with more than $m$ vertices, \\then $c_1(G) \leq \lceil m /2 \rceil$. \hfill [Joret, Kami{\'n}ski, and Theis'10]
\end{itemize}
\end{frame}

\begin{frame}{Known Results}{for general $s$}
\begin{itemize}
\item For every fixed $s$, computing $c_s(G)$ is NP-hard in general, \\ but is in P when $G$ is an interval graph. \\ \hfill [Fomin, Golovach, Kratochv{\'{\i}}l'08]
\item  When $s>1$, there is no constant upper bound \\ for $c_s(G)$ when $G$ is a planar graphs. \hfill [Nisse and Suchan'08]
\end{itemize}
\pause
In my thesis, I further studied this game, especially the case $s>1$.
\end{frame}

\begin{frame}{Notation}
\begin{description}
\item[$G$] the graph of the game, which is simple and connected.
\item[$n$] the number of vertices of $G$.
\item[$s$] is the speed of the robber.
\end{description}
\end{frame}

\section{Robber With Finite Speed}

%\section{Maximum Cop Number of Connected Graphs}

\begin{frame}{Meyniel's Conjecture}
\begin{block}{Meyniel's Conjecture, 1987}
For every graph $G$ on $n$ vertices, $$c_1(G) = O (\sqrt n)$$
\end{block}
\begin{itemize}
\item The best known bound  is
$$c_1(G) \leq n 2 ^{-(1-o(1)) \sqrt {\log_2 n}} = n^{1-o(1)}$$
\hfill [Lu and Peng'09, Scott and Sudakov'10]
\item There exist graphs with $c_1(G) = \Omega(\sqrt n)$.
\end{itemize}

\pause
For general $s$:
\begin{itemize}
\item For every fixed $s$, there exist graphs with $c_s(G) =\Omega\left( n^{s-3 / s-2}\right)$. \hfill[Frieze, Krivelevich, Loh'11]
\item We will show there exist graphs with $c_s(G) = \Omega \left(n^{s/s+1}\right)$.
\end{itemize}
\end{frame}

\begin{frame}{Controlling a Path}
\begin{definition}
The cops \alert{control} a vertex if there is a cop at that vertex
or at an adjacent vertex.\\
The cops {control} a path if they control some vertex of it.
\end{definition}
\end{frame}

\begin{frame}{Maximum Cop Number of Connected Graphs}{When $s\in \{2,4\}$}
\begin{lemma}
Let $G$ be $d$-regular with {girth} $> 2s+2$.
Then $c_s(G) = \Omega(d^s)$.
\end{lemma}
\pause
\begin{proof}
Vertex $r$ is \alert{safe} if $\exists X\subseteq V$, $|X| = (d-1)^s / 2$, such that \\
$\forall x\in X$, $\exists (r,x)$-path of length $s$ not \alert{controlled} by the cops:
\begin{center}
\begin{tikzpicture}[scale = 0.8] {thin}
\node at (-0.25,0) {$r$};
\node at (3,-1.5){$X$};
\foreach \x in {-0.75,-0.25,0.25,0.75} {
    \draw [decorate, decoration = {random steps, segment length = 10 pt, amplitude = 3 pt}] (0,0) -- (3,\x);
    \node at (3,\x) [graphnode]{};
}
\draw (3,0) ellipse (10 pt and 35 pt);
\node at (0,0) [robber]{};
\node at (4.3,0.5) [cop] {};
\node at (6,1.25) [cop] {};
\node at (3.7, -0.75) [cop] {};
\node at (5, -0.25) [cop] {};
\end{tikzpicture}
\end{center}
\end{proof}

\end{frame}

\begin{frame}{Maximum Cop Number of Connected Graphs}{When $s\in \{2,4\}$}
\begin{lemma}
Let $G$ be $d$-regular with girth $> 2s+2$.
Then $c_s(G) = \Omega(d^s)$.
\end{lemma}
\begin{proof}
Vertex $r$ is {safe} if $\exists X\subseteq V$, $|X| = (d-1)^s / 2$, such that \\
$\forall x\in X$, $\exists (r,x)$-path of length $s$ not controlled by the cops:
\begin{center}
\begin{tikzpicture}[scale = 0.8] {thin}
\node at (-0.25,0) {$r$};
\node at (3,-1.5){$X$};
\foreach \x in {-0.75,-0.25,0.25,0.75} {
    \draw [decorate, decoration = {random steps, segment length = 10 pt, amplitude = 3 pt}] (0,0) -- (3,\x);
    \node at (3,\x) [graphnode]{};
}
\draw (3,0) ellipse (10 pt and 35 pt);
\node at (0,0) [robber]{};
\node at (4,0.5) [cop] {};
\node at (6,1) [cop] {};
\node at (3.7, -1) [cop] {};
\node at (5, 0) [cop] {};
\pause
\foreach \x in {-0.75,-0.25,0.25,0.75} {
    \draw [decorate, decoration = {random steps, segment length = 10 pt, amplitude = 1 pt}] (6,\x-0.15) -- (3,\x);
    \draw [decorate, decoration = {random steps, segment length = 10 pt, amplitude = 1 pt}] (6,\x+0.15) -- (3,\x);
}
\end{tikzpicture}
\end{center}
\pause
\vspace{-0.5cm}
After their move, each cop controls $\leq (s+2)d^s$ escaping paths.
\end{proof}
\end{frame}

\begin{frame}{Maximum Cop Number of Connected Graphs}{When $s\in \{2,4\}$}
\begin{lemma}
Let $G$ be $d$-regular with girth $> 2s+2$.
Then $c_s(G) = \Omega(d^s)$.
\end{lemma}
\begin{theorem}
Let $s\in \{2,4\}$ be fixed.
For every $n$, there exists a graph on $n$ vertices with $c_s(G) = \Omega\left(n^{s/s+1}\right)$.
\end{theorem}
\pause
\begin{proof}
\begin{description}
\item[$s=2$] There exist $d$-regular graphs on $\leq 2d^3$ vertices with girth 7.
\hfill [Lazebnik, Ustimenko, Woldar'97]
\item[$s=4$] There exist $d$-regular graphs on $\leq 2d^5$ vertices with girth 12.
\hfill [Araujo, Gonz\'{a}lez, Montellano-Ballesteros, Serra'07]
\end{description}
\end{proof}
\end{frame}

\begin{frame}{Maximum Cop Number of Connected Graphs}{For general $s$}
\begin{lemma}
Let $G$ be $d$-regular bipartite graph with diameter larger than $s$, such that
\begin{enumerate}
\item If $u$ and $v$ are vertices of distance $\leq s+1$,
there are $O(1)$ distinct shortest $(u,v$)-paths.
\item For every vertex $u$ and subset $A$ of vertices,
there exist $\Omega(d^s)$ vertices $x$ of distance $s$ from $u$,
where any shortest $(u,x)$-path avoids $A$.
\end{enumerate}
Then $c_s(G) = \Omega (d^s)$.
\end{lemma}
\end{frame}

\begin{frame}{Maximum Cop Number of Connected Graphs}{For general $s$}
\begin{theorem}
Let $s$ be fixed.
For every $n$, there exists a graph on $n$ vertices with $c_s(G) = \Omega\left(n^{s/s+1}\right)$.
\end{theorem}
\pause
\begin{proof}
For $d$ large enough, there exist Cayley graphs on $O(d^{s+1})$ vertices satisfying the conditions of the lemma.
\end{proof}
Remark: This result was proved jointly with Noga Alon.
\end{frame}

\begin{frame}{A Generalization of Meyniel's Conjecture}
\begin{theorem}
Let $s$ be fixed.
For every $n$, there exists a graph on $n$ vertices with $c_s(G) = \Omega\left(n^{s/s+1}\right)$.
\end{theorem}
\begin{block}{Conjecture}
For every graph $G$ on $n$ vertices, $c_s(G) = O\left(n^{s/s+1}\right)$.
\end{block}
\begin{block}{[Meyniel's Conjecture, 1987]}
For every graph $G$ on $n$ vertices, $c_1(G) = O (\sqrt n)$.
\end{block}
\end{frame}


\section{Infinitely Fast Robber}

\begin{frame}{Infinitely Fast Robber}
\begin{definition}
Let $G$ be a connected graph on $n$ vertices. Then
$$c_{\infty}(G) = c_n (G)$$
And we call $c_{\infty}(G)$ the \alert{cop number} of $G$.\\
If the robber has speed $n$,\\
we say the robber is \alert{infinitely fast}.
\end{definition}
\end{frame}

\begin{frame}{Known Results}{for infinitely fast robber}
\begin{itemize}
\item Computing $c_{\infty}(G)$ is NP-hard.\\ \hfill [Fomin, Golovach, Kratochv{\'{\i}}l'08]
\item For every $n$, there exists a graph on $n$ vertices with $c_{\infty}(G) = \Theta\left(n\right)$. \hfill[Frieze, Krivelevich, Loh'11]
\end{itemize}
\pause
For the rest of the talk, we will assume the robber is infinitely fast.
\end{frame}

\begin{frame}{An Obvious Bound For The Cop Number}
\begin{definition}
Set $X\subseteq V(G)$ is a \alert{dominating set} if every vertex is either in $X$ or adjacent to a vertex in $X$.\\
The \alert{domination number} of graph $G$ is the minimum size of a dominating set of $G$.
\end{definition}
\pause
\begin{block}{Proposition}
The cop number $\leq$ the domination number.
\end{block}
\begin{proof}
The cops start at a dominating set.
They will capture the robber in the first move.
\end{proof}
\end{frame}

\subsection{Relation with treewidth}

\begin{frame}{The Treewidth of a Graph}
\begin{definition}
\small
Let $G$ be a graph, $T$ be a tree, and $\{W_t : t\in V(T)\}$
be a family of subsets of $V(G)$, called the \alert{bags}.\\
The pair $(T,W)$ is a \alert{tree decomposition} of $G$ if it satisfies:
\begin{itemize}
\item [(i)] $\displaystyle \cup_{t\in V(T)} W_t = V(G)$.
\item [(ii)] Forall $uv\in E(G)$, there is a bag containing both $u$ and $v$.
\item [(iii)] Forall $v\in V(G)$ the set of bags containing $v$ induces a subtree of $T$
\end{itemize}
The \alert{width} of $(T,W)$ is the maximum size of a bag, minus 1.\\
The \alert{treewidth} of $G$, written \alert{$tw(G)$}, is the minimum number $w$
such that $G$ has a tree decomposition having width $w$.
\end{definition}
Treewidth quantifies how much is $G$ similar to a tree. \\
for example, a tree has treewidth 1.
\end{frame}

\begin{frame}{The Relation Between Cop Number and Treewidth}
\begin{block}{Proposition}
For any $G$, $$c_{\infty}(G) \leq tw(G)+1$$
\end{block}
\begin{center}
\begin{tikzpicture}[thin]
\draw (0,0) -- (-1.5, 1);
\draw (-1.5,1) -- (-0.5, 1.5);
\draw (-1.5,1) -- (-2.5, 1.5);
\draw (-1.5,1) -- (-2,-1);
\draw(0,0) -- (-1,-1);
\draw(0,0) -- (1,1);
\draw (0,0) -- (1.5, -0.5);
\draw (1.5,-0.5) -- (2.5,0);
\filldraw [fill=white] (0,0) circle (10pt);
\filldraw [fill=white](-1.5,1) circle (10pt);
\filldraw [fill=white](-2.5, 1.5) circle (10pt);
\filldraw [fill=white](-0.5, 1.5) circle (10pt);
\filldraw [fill=white](-2, -1) circle (10pt);
\filldraw [fill=white](-1, -1) circle (10pt);
\filldraw [fill=white](1, 1) circle (10pt);
\filldraw [fill=white](1.5, -0.5) circle (10pt);
\filldraw [fill=white](2.5, 0) circle (10pt);
\pause
\visible<2>
{
\foreach \x in {-1,1} {
    \foreach \y in {-1,1} {
        \node at (-2 + \x*0.15, -1 + \y*0.15) [cop] {};
    }
}
\node at (1 - 0.15,1+0.15) [robber] {};
}
\visible<3>
{
\filldraw [fill=white] (0,0) circle (10pt);
\filldraw [fill=white](-1.5,1) circle (10pt);
\filldraw [fill=white](-2.5, 1.5) circle (10pt);
\filldraw [fill=white](-0.5, 1.5) circle (10pt);
\filldraw [fill=white](-2, -1) circle (10pt);
\filldraw [fill=white](-1, -1) circle (10pt);
\filldraw [fill=white](1, 1) circle (10pt);
\filldraw [fill=white](1.5, -0.5) circle (10pt);
\filldraw [fill=white](2.5, 0) circle (10pt);
\foreach \x in {-1,1} {
    \foreach \y in {-1,1} {
        \node at (-1.5 + \x*0.15, 1 + \y*0.15) [cop] {};
    }
}
\node at (1.5 - 0.15,-0.5-0.15) [robber] {};
}
\visible<4>{
\filldraw [fill=white] (0,0) circle (10pt);
\filldraw [fill=white](-1.5,1) circle (10pt);
\filldraw [fill=white](-2.5, 1.5) circle (10pt);
\filldraw [fill=white](-0.5, 1.5) circle (10pt);
\filldraw [fill=white](-2, -1) circle (10pt);
\filldraw [fill=white](-1, -1) circle (10pt);
\filldraw [fill=white](1, 1) circle (10pt);
\filldraw [fill=white](1.5, -0.5) circle (10pt);
\filldraw [fill=white](2.5, 0) circle (10pt);
\foreach \x in {-1,1} {
    \foreach \y in {-1,1} {
        \node at (0 + \x*0.15, 0 + \y*0.15) [cop] {};
    }
}
\node at (2.5 + 0.15,0 + 0.15) [robber] {};
}
\visible<5>{
\filldraw [fill=white] (0,0) circle (10pt);
\filldraw [fill=white](-1.5,1) circle (10pt);
\filldraw [fill=white](-2.5, 1.5) circle (10pt);
\filldraw [fill=white](-0.5, 1.5) circle (10pt);
\filldraw [fill=white](-2, -1) circle (10pt);
\filldraw [fill=white](-1, -1) circle (10pt);
\filldraw [fill=white](1, 1) circle (10pt);
\filldraw [fill=white](1.5, -0.5) circle (10pt);
\filldraw [fill=white](2.5, 0) circle (10pt);
\foreach \x in {-1,1} {
    \foreach \y in {-1,1} {
        \node at (1.5 + \x*0.15, -0.5 + \y*0.15) [cop] {};
    }
}
\node at (2.5 +0.15,0-0.15) [robber] {};
}
\end{tikzpicture}
\end{center}
\end{frame}

\begin{frame}{Helicopter Cops and Robber Game}

\begin{definition} [Helicopter Cops and Robber Game]
\begin{itemize}
\item There is a set of cops and a robber.
\item It is a {continuous-time} game.
\item At any moment, the robber is at a vertex.
\item At any moment, each cop is either
\begin{itemize}
\item standing at a vertex, or
\item in a helicopter.
\end{itemize}
\item The cops want to land via a helicopter on the robber's vertex.
\item The robber can see the helicopter approaching its landing spot,
and may run along a cop-free path to a new vertex.
\end{itemize}

\end{definition}

\pause
In a complete graph, $n$ cops are needed.\\
In a path, 2 cops are needed.

\end{frame}

\begin{frame}{A Lower Bound for Cop Number}
{Using helicopter cops and robber Game}
\begin{theorem}[Seymour and Thomas'93]
Exactly $tw(G)+1$ cops are needed to capture the robber in the Helicopter Cops and Robber game.
\end{theorem}
\pause
\begin{theorem}
For every graph $G$ with maximum degree $\Delta$,
$${tw(G) + 1} \leq c_{\infty}(G) ({\Delta + 1})$$
\end{theorem}
\pause
Punchline: If the robber is able to predict the movement of the cops,
the number of required cops is at most multiplied by $\Delta+1$.
\end{frame}

\begin{frame}{The $m$-Dimensional Hypercube}

\begin{definition}
The \alert{$m$-dimensional hypercube}, or the \alert{$m$-cube},
has vertex set $\{0,1\}^m$
with two vertices being adjacent if they differ in exactly one coordinate.
\end{definition}

\begin{example}
\begin{center}
\begin{tikzpicture}
    \node at (0,0) [graphnode] {};
    \node at (0,1) [graphnode] {};
    \node at (0,-0.5) {1-cube};
    \draw(0,0) -- (0,1) ;

    \node at (2,0) [graphnode] {};
    \node at (2,1) [graphnode] {};
    \node at (3,0) [graphnode] {};
    \node at (3,1) [graphnode] {};
    \draw (2,0) -- (3,0) -- (3,1) -- (2,1) -- (2,0);
    \node at (2.5,-0.5) {2-cube};

    \node at (5,0) [graphnode] {};
    \node at (5.5,0.5) [graphnode] {};
    \node at (6,1) [graphnode] {};
    \node at (6.5,1.5) [graphnode] {};
    \node at (5,1.5) [graphnode] {};
    \node at (5.5,1) [graphnode] {};
    \node at (6,0.5) [graphnode] {};
    \node at (6.5,0) [graphnode] {};
    \draw (5,0) -- (6.5,0) -- (6.5, 1.5) -- (5, 1.5) -- (5,0) -- (5.5, 0.5) -- (6, 0.5) -- (6,1) -- (5.5, 1) -- (5.5, 0.5);
    \draw (6,0.5) -- (6.5, 0);
    \draw (6,1) -- (6.5, 1.5);
    \draw (5,1.5) -- (5.5,1);
    \node at (6,-0.5) {3-cube};

\end{tikzpicture}
\end{center}
\end{example}

\end{frame}

\begin{frame}{The Cop Number of The $m$-dimensional Hypercube}

\begin{theorem}[from previous slides]
For every graph $G$ with treewidth $tw$ and maximum degree $\Delta$,
$$\frac{tw + 1}{\Delta + 1} \leq c_{\infty}(G)$$
\end{theorem}

\pause

\begin{corollary}
If $G$ is the $m$-dimensional hypercube with $n=2^m$ vertices, then
$$ \frac{\eta_1 n}{m\sqrt{m}} \leq c_{\infty}(G) \leq \frac{\eta_2 n}{m}$$
\end{corollary}
\pause
\begin{proof}
$tw(G) = \Theta(n/\sqrt{m})$ [Sunil Chandran, Kavitha'06],
$\Delta = m$, and domination number $=O(n/m)$.
\end{proof}
\end{frame}

\subsection{Interval graphs}

\begin{frame}{Interval Graphs}
\begin{definition}
Consider a set of closed intervals on the real line.
Put a vertex for each interval, and join two vertices
if their corresponding intervals intersect.
The result is an \alert{interval graph}.
\end{definition}
\end{frame}

\begin{frame}{Known Results}{for interval graphs}
\begin{itemize}
\item For every fixed finite $s$, computing $c_s(G)$ is NP-hard \\when $G$ is a general graph.
\item If $G$ is an interval graph, then $$c_s(G) \leq 5s - 1$$
\item Leads to a polynomial algorithm for fixed finite $s$. \\ \hfill [Fomin, Golovach, Kratochv{\'{\i}}l'08]
\pause
\item For $s=\infty$, the complexity for interval graphs is open.
\item We give a 3-approximation algorithm.
\end{itemize}
\end{frame}

\begin{frame}{A Path Decomposition of a Graph}
\begin{definition}
Let $G$ be a graph, $m$ be a positive integer, and $\{W_i : 1\leq i \leq m\}$
be a family of subsets of $V(G)$, called the \alert{bags}.
The family $\{W_i\}$ is a \alert{path decomposition} of $G$ if it satisfies:
\begin{itemize}
\item [(i)] $\cup_{1\leq i \leq m} W_i = V(G)$.
\item [(ii)] For every $uv\in E(G)$, there is a bag containing both $u$ and $v$.
\item [(iii)] For every $v\in V(G)$, $v$ is contained in a consecutive set of bags.
\end{itemize}
\end{definition}
\pause
Fact: Every interval graph $G$ has a path decomposition,
in which every bag induces a clique in $G$.
\end{frame}

\begin{frame}{3-Approximation For Interval Graphs}
\begin{definition}
A subgraph $H$ of $G$ is \alert{$k$-wide} if
\begin{enumerate}
\item [(i)]  $H$ is $k$-vertex-connected, and
\item [(ii)] No $k-1$ vertices of $G$ dominate $H$.
\end{enumerate}
Let \alert{$M$} be the maximum number s.~t.~$G$ has an $M$-wide subgraph.
\end{definition}
\pause
\begin{lemma}
$$M \leq c_{\infty}(G) \leq 3M$$
\end{lemma}
\pause
{
\small
\begin{proof}[Proof (lower bound)]
Assume $H$ be $M$-wide, and there are $< M$ cops in the game.
\pause
The robber stays in $H$ all the time.
In every round, there is an uncontrolled vertex in $H$, and $M$ disjoint paths to go there.
\end{proof}
}
\end{frame}

\begin{frame}{3-Approximation For Interval Graphs}

\begin{lemma}
If {$M$} is the maximum number s.~t.~$G$ has an $M$-wide subgraph,
$$M \leq c_{\infty}(G) \leq 3M$$
\end{lemma}
\pause
\begin{proof}[Proof (upper bound)]
For each subgraph $H$ of $G$, at least one of the following holds:
\begin{itemize}
\item [(i)]  $H$ has a cut set with $M$ vertices.
\item [(ii)] There are $M$ vertices of $G$ that dominate $H$.
\end{itemize}
\begin{center}
\begin{tikzpicture}[thin]
\visible<3-7>{
\draw (-5.5,0) -- (5.2, 0);
\filldraw [fill=white] (0,0) circle (10pt);
\filldraw [fill=white](-1.5,0) circle (10pt);
\filldraw [fill=white](-3, 0) circle (10pt);
\filldraw [fill=white](1.5, 0) circle (10pt);
\filldraw [fill=white](3, 0) circle (10pt);
\filldraw [fill=white](4.5, 0) circle (10pt);
\filldraw [fill=white](-4.5, 0) circle (10pt);
}
\visible<4-5>
{
\foreach \z in {-4.5} {
\foreach \x in {-1,1} {
    \foreach \y in {-1,1} {
        \node at (\z + \x*0.15, 0 + \y*0.15) [cop] {};
    }
}
}

\foreach \x in {0} {
    \foreach \y in {-1,1} {
        \node at (3 + \x*0.15, 0 + \y*0.15) [cop] {};
    }
}

\node at (0 - 0.15,0+0.15) [robber] {};
}

\visible<5-6>
{
    \node at (0 - 0.15, 0 + 0.15) [cop] {};
    \node at (0 + 0.15, 0 + 0.15) [cop] {};
    \node at (0 -0.15, 0 -0.15) [cop] {};
}

\visible<5>{\node at (-1.5 + 0.15,0-0.15) [robber] {};}

\visible<6>
{
\filldraw [fill=white] (0,0) circle (10pt);
\filldraw [fill=white](-1.5,0) circle (10pt);
\filldraw [fill=white](-3, 0) circle (10pt);
\filldraw [fill=white](1.5, 0) circle (10pt);
\filldraw [fill=white](3, 0) circle (10pt);
\filldraw [fill=white](4.5, 0) circle (10pt);
\filldraw [fill=white](-4.5, 0) circle (10pt);

\foreach \z in {-4.5} {
\foreach \x in {-1,1} {
    \foreach \y in {-1,1} {
        \node at (\z + \x*0.15, 0 + \y*0.15) [cop] {};
    }
}
}
    \node at (0 - 0.15, 0 + 0.15) [cop] {};
    \node at (0 + 0.15, 0 + 0.15) [cop] {};
    \node at (0 -0.15, 0 -0.15) [cop] {};
    \node at (-3 + 0.15,0+0.15) [robber] {};
}

\visible<7>
{
\filldraw [fill=white] (0,0) circle (10pt);
\filldraw [fill=white](-1.5,0) circle (10pt);
\filldraw [fill=white](-3, 0) circle (10pt);
\filldraw [fill=white](1.5, 0) circle (10pt);
\filldraw [fill=white](3, 0) circle (10pt);
\filldraw [fill=white](4.5, 0) circle (10pt);
\filldraw [fill=white](-4.5, 0) circle (10pt);

\foreach \z in {-4.5} {
\foreach \x in {-1,1} {
    \foreach \y in {-1,1} {
        \node at (\z + \x*0.15, 0 + \y*0.15) [cop] {};
    }
}
}
    \node at (0 - 0.15, 0 + 0.15) [cop] {};
    \node at (0 + 0.15, 0 + 0.15) [cop] {};
    \node at (0 -0.15, 0 -0.15) [cop] {};
    \node at (-1.5 - 0.15,0-0.15) [robber] {};
    \node at (-1.5 + 0.15, 0 + 0.15) [cop] {};
    \node at (-3 - 0.15, 0 + 0.15) [cop] {};
}
\end{tikzpicture}
\end{center}
\visible<4-7>{
\alert{Invariant:} Two teams keep the robber in the ``interval subgraph.''
}
\end{proof}
\end{frame}

\begin{frame}{3-Approximation For Interval Graphs}
\begin{definition}
A subgraph $H$ of $G$ is {$k$-wide} if
\begin{enumerate}
\item [(i)]  $H$ is $k$-vertex-connected, and
\item [(ii)] No $k-1$ vertices of $G$ dominate $H$.
\end{enumerate}
Let {$M$} be the maximum number s.~t.~$G$ has an $M$-wide subgraph.
\end{definition}
\begin{lemma}
It is possible to calculate $M$ in polynomial time.
\end{lemma}
\pause
\begin{proof}
The number of interval subgraphs is $O(n^2)$.\\
\pause
Each of them is an interval graph, and its dominating number and connectivity can be found in polynomial time.
\end{proof}
\end{frame}

\begin{frame}{3-Approximation For Interval Graphs}
Let $M$ be the maximum number s.~t.~$G$ has an $M$-wide subgraph.
$$M \leq c_{\infty}(G) \leq 3M$$
and it is possible to calculate $M$ in polynomial time.
Thus,
\begin{theorem}
There is a polynomial time
3-approximation algorithm for finding the cop number of an interval graph.
\end{theorem}
\end{frame}

\begin{frame}{Maximum Cop Number of Interval Graphs}
\begin{theorem}
Let $G$ be an interval graph.
No subgraph of $G$ is $(\sqrt{5n}+3)$-wide.
Hence $$c_{\infty}(G) = O(\sqrt n)$$
\end{theorem}
\pause
The theorem is asymptotically tight:
\begin{center}
\begin{tikzpicture}

\foreach \x in {-4,-2,0,2,4} {
    \draw (\x-0.3,-0.3) -- (\x+0.3,-0.3) -- (\x+0.3,0.3) -- (\x-0.3,0.3) -- (\x-0.3,-0.3) -- (\x+0.3,0.3) -- (\x+0.3,-0.3) -- (\x-0.3,0.3);
    \draw(\x,0) circle (16pt);
    \foreach \y in {-0.3,0.3} {
        \foreach \z in {-0.3, 0.3} {
            \node at (\x + \y, 0 + \z) [graphnode] {};
        }
    }
}

\node at (-5,0) {$K_{3m}$};

\node at (-4,-1) {1};
\node at (-2,-1) {2};
\node at (-1,-1) {$\dots$};
\node at (4,-1) {$m$};

\foreach \x in {-4,-2,0,2} {
    \foreach \y in {-0.3,0.3} {
        \foreach \z in {-0.3, 0.3} {
            \foreach \w in {-0.3,0.3} {
                \foreach \q in {-0.3, 0.3} {
            \draw (\x + \y, 0 + \z) -- (\x + 2 + \w, 0+\q) ;
        }}}
    }

}

\end{tikzpicture}
\end{center}
The above graph is $\left(\frac{\sqrt n}{3}\right)$-wide.
\end{frame}


\subsection{Chordal graphs}

\begin{frame}{Chordal Graphs}
\begin{definition}
Graph $G$ is \alert{chordal} if it does not have an induced cycle with more than 3 vertices.
\end{definition}

\begin{example}

\begin{center}
\begin{tikzpicture}[thin, scale = 0.5]
        \draw (0,0) -- (-1,1) -- (-1,2) -- (0,3) -- (1,2) -- (1,1) -- (1,2) -- (-1,2) -- (1,1) -- (0,0) -- (1,1) -- (-1,1);
		\node at (0,0) [graphnode]{};
		\node at (-1,1) [graphnode]{};
		\node at (-1,2) [graphnode]{};
		\node at (0,3) [graphnode]{};
		\node at (1,2) [graphnode]{};
		\node at (1,1) [graphnode]{};
		\node at (1,2) [graphnode]{};

%        \draw[dashed](1,1.5) ellipse(15pt and 30pt);
%        \node at (1.6,0) {$X_1$};
        \node at (0,-1) {chordal};

        \draw (9,1) -- (10,1) -- (10,2) -- (9,2) -- (11,3) -- (11,0) -- (9,1);
        \draw (10,2) -- (11,3);
		\node at (9,1) [graphnode]{};
		\node at (10,1) [graphnode]{};
		\node at (10,2) [graphnode]{};
		\node at (9,2) [graphnode]{};
		\node at (11,3) [graphnode]{};
		\node at (11,0) [graphnode]{};
		\node at (9,2) [graphnode]{};

%        \draw[dashed](9,1.5) ellipse(15pt and 30pt);
%        \node at (8.3, 0) {$X_2$};
        \node at (10,-1) {not chordal};
\end{tikzpicture}
\end{center}
\end{example}
\pause
Fact: Every interval graph is chordal.
\end{frame}

\begin{frame}{Maximum Cop Number of Chordal Graphs}
As we saw, the cop number of an interval graph is $O(\sqrt n)$.\\
What about the cop number of a chordal graph?\\
\pause
Next we show there are chordal graphs with cop number $\Omega \left(\frac{n}{\log n}\right)$.
\end{frame}

\begin{frame}{Accessible Sets}
\begin{definition}
A subset $X \subseteq V(G)$ is called \alert{accessible} if
\begin{itemize}
\item $c_{\infty}(G) \geq |X|$, and
\item if there are $|X|-1$ cops in the game, then there exists a strategy for the robber,
in which the robber has access to $X$ in every round.
That is, in every round, the cops are not separating the robber from $X$.
\end{itemize}
\end{definition}
\pause
\begin{example}

\begin{center}
\begin{tikzpicture}[thin, scale = 0.5]
        \draw (0,0) -- (-1,1) -- (-1,2) -- (0,3) -- (1,2) -- (1,1) -- (1,2) -- (-1,2) -- (1,1) -- (0,0);
		\node at (0,0) [graphnode]{};
		\node at (-1,1) [graphnode]{};
		\node at (-1,2) [graphnode]{};
		\node at (0,3) [graphnode]{};
		\node at (1,2) [graphnode]{};
		\node at (1,1) [graphnode]{};
		\node at (1,2) [graphnode]{};

        \draw[dashed](1,1.5) ellipse(15pt and 30pt);
        \node at (1.6,0) {$X_1$};
        \node at (-2,1) {$G_1$};

        \draw (9,1) -- (10,1) -- (10,2) -- (9,2) -- (11,3) -- (11,0) -- (9,1);
		\node at (9,1) [graphnode]{};
		\node at (10,1) [graphnode]{};
		\node at (10,2) [graphnode]{};
		\node at (9,2) [graphnode]{};
		\node at (11,3) [graphnode]{};
		\node at (11,0) [graphnode]{};
		\node at (9,2) [graphnode]{};

        \draw[dashed](9,1.5) ellipse(15pt and 30pt);
        \node at (8.3, 0) {$X_2$};
        \node at (12,1) {$G_2$};
\end{tikzpicture}
\end{center}
\end{example}

\end{frame}

\begin{frame} {Construction of Chordal Graphs With Large Cop Number}
$X$ is accessible in this graph:

\begin{center}
\begin{tikzpicture}[thin, scale = 0.8]
        \draw (0,0) -- (-1,1) -- (-1,2) -- (0,3) -- (1,2) -- (1,1) -- (1,2) -- (-1,2) -- (1,1) -- (0,0);
		\node at (0,0) [graphnode]{};
		\node at (-1,1) [graphnode]{};
		\node at (-1,2) [graphnode]{};
		\node at (0,3) [graphnode]{};
		\node at (1,2) [graphnode]{};
		\node at (1,1) [graphnode]{};
		\node at (1,2) [graphnode]{};

        \draw[dashed](1,1.5) ellipse(15pt and 27pt);
        \node at (0.9,0.2) {$X_1$};
        \node at (0,-1) {$G_1$};

        \draw (9,1) -- (10,1) -- (10,2) -- (9,2) -- (11,3) -- (11,0) -- (9,1);
		\node at (9,1) [graphnode]{};
		\node at (10,1) [graphnode]{};
		\node at (10,2) [graphnode]{};
		\node at (9,2) [graphnode]{};
		\node at (11,3) [graphnode]{};
		\node at (11,0) [graphnode]{};
		\node at (9,2) [graphnode]{};

        \draw[dashed](9,1.5) ellipse(15pt and 27pt);
        \node at (9.2, 0.2) {$X_2$};
        \node at (10,-1) {$G_2$};

        \foreach \x in {3,5,7} {
            \foreach \y in {0,1,2,3} {
                \node at (\x, \y) [graphnode]{};
            }
        }

        \foreach \y in {0,1,2,3} {
            \foreach \z in {0,1,2,3} {
                \draw(3,\y) -- (5,\z);
                \draw(5,\y) -- (7,\z);
                \draw(3,\y) -- (1,1);
                \draw(3,\y) -- (1,2);
                \draw(7,\y) -- (9,1);
                \draw(7,\y) -- (9,2);
            }
        }
        %\draw [dashed, rounded corners = 7mm] (-1.8,-0.5) rectangle (2,3.5);
        \foreach \x in {3,5,7} {
            \draw [dashed, rounded corners = 3mm] (\x - 0.6, -0.5) rectangle (\x + 0.6, 3.5);
        }
        %\draw [dashed, rounded corners = 7mm] (8,-0.5) rectangle (12,3.5);
        \node at (3,-1) {$K_4$};
        \node at (5,-1) {$K_4$};
        \node at (5,4) {$X$};
        \node at (7,-1) {$K_4$};

\visible<2>{
\node at (-1,2) [cop] {};
\node at (0,0) [robber] {};
\node at (9,2) [cop] {};
\node at (7,1) [cop] {};
}

\visible<3>{
\node at (-1,1) [cop] {};
\node at (0,0) [robber] {};
\node at (10,2) [cop] {};
\node at (5,2) [cop] {};
}

\visible<4>{
\node at (-1,1) [cop] {};
\node at (0,3) [robber] {};
\node at (10,2) [cop] {};
\node at (5,2) [cop] {};
}

\visible<5>{
\node at (-1,1) [cop] {};
\node at (0,3) [robber] {};
\node at (10,1) [cop] {};
\node at (3,1) [cop] {};
}

\visible<6>{
\node at (-1,1) [cop] {};
\node at (11,3) [robber] {};
\node at (10,1) [cop] {};
\node at (3,1) [cop] {};
}

\end{tikzpicture}
\end{center}
\end{frame}

\begin{frame}{The Maximum Cop Number of Chordal Graphs}
\begin{theorem}
There exist chordal graphs with cop number $\Omega \left( \frac{n}{\log n}\right)$.
\end{theorem}
\pause
\begin{proof}
Let $g(m)$ be the minimum size of a graph with an accessible subset of $m$ vertices.
\pause
One can build a graph with an accessible subset of $2m$ vertices
by using two graphs with accessible subsets of $m$ vertices,
and 3 copies of $K_{2m}$.
\pause
Hence we have
$$g(2m) \leq 2 g(m) + 3 \times 2m$$
so $g(m) = O(m \log m)$.
\pause
Thus there are chordal graphs on $O(m\log m)$ vertices with cop number $\geq m$.
\end{proof}
\end{frame}


\subsection{Expander graphs and random graphs}

\begin{frame}{The Closed Neighbourhood of a Subset}
\begin{definition}
Let $S\subseteq V(G)$.
The \alert{(closed) neighbourhood} of $S$, written \alert{$\overline{N}(S)$},
is the set of vertices that are in $S$ or have a neighbour in $S$.
\end{definition}
\pause
\begin{example}
\begin{center}
\begin{tikzpicture}[thin, scale = 0.5]
        \draw (0,0) -- (-1,1) -- (-1,2) -- (0,3) -- (1,2) -- (1,1) -- (1,2) -- (-1,2) -- (1,1) -- (0,0);
		\node at (0,0) [graphnode]{};
		\node at (-1,1) [graphnode,draw=green!100,fill=green!100]{};
		\node at (-1,2) [graphnode,draw=green!100,fill=green!100]{};
		\node at (0,3) [graphnode,draw=green!100,fill=green!100]{};
		\node at (1,2) [graphnode,draw=green!100,fill=green!100]{};
		\node at (1,1) [graphnode,draw=green!100,fill=green!100]{};
		\node at (1,2) [graphnode,draw=green!100,fill=green!100]{};
        \draw[dashed](0,2.5) ellipse(50pt and 30pt);
        \node at (-2.3,2.5) {$S_1$};

\pause
        \draw (9,1) -- (10,1);
        \draw (10,2) -- (9,2) -- (11,3) -- (11,0) -- (9,1);
		\node at (9,1) [graphnode]{};
		\node at (10,1) [graphnode]{};
		\node at (10,2) [graphnode,draw=green!100,fill=green!100]{};
		\node at (9,2) [graphnode,draw=green!100,fill=green!100]{};
		\node at (11,3) [graphnode,draw=green!100,fill=green!100]{};
		\node at (11,0) [graphnode,draw=green!100,fill=green!100]{};
		\node at (9,2) [graphnode,draw=green!100,fill=green!100]{};

        \draw[dashed](10,2.5) ellipse(50pt and 30pt);
        \node at (10-2.3,2.5) {$S_2$};

\end{tikzpicture}
\end{center}
\end{example}
\end{frame}

\begin{frame}{The Large Component Lemma}
\begin{lemma}
Assume that for every subset $S$ of vertices of size $\leq m$,
$G-\overline{N}(S)$ has a connected component of size $> n/2$.
Then $c_{\infty}(G) > m$.
\end{lemma}
\pause
\begin{proof}
{\small
Let there be $m$ cops.
We give an escaping strategy for robber:\\
\alert{Invariant:} Robber in largest component of $G-\overline{N}(S)$, $S=$ cops' position}
\pause
\begin{center}
\begin{tikzpicture}[thin]

\visible<3-4>{

\draw (0,0) ellipse (10 pt and 20 pt);
\node at (0,-1.2) {$\overline{N}(S)$};
\draw [fill=green!100] (1.5,1) ellipse (25 pt and 15 pt);
\node at (3,1.2) {$C$};
\draw (1.5,0) ellipse (10 pt and 5 pt);
\draw (1.5,-1) ellipse (10 pt and 5 pt);

\draw (0.2, 0.2) -- (1, 0.8);
\draw (0, 0.5) -- (1, 1.2);
\draw (0.2,0) -- (1.3, 0);
\draw (0, -0.5) -- (1.4, -1);

\node at (1.7,1.2) [robber] {};
}

\visible<3>{
\node at (-0.2,-0.2) [cop] {};
\node at (-0.2,0.2) [cop] {};
\node at (0, -0.3) [cop] {};
}

\visible<4-6> {
    \node at (0.1,0.1) [cop] {};
    \node at (0,0.5) [cop] {};
    \node at (-0.1, 0.3) [cop] {};
}

\visible<5-6> {
\filldraw [fill=green!100,draw=green!10] (1.5,1) ellipse (25 pt and 15 pt);
\draw [rotate around = {-45:(0.5,0.6)}] (0.5,0.6) ellipse (15 pt and 30 pt);
\node at (-1,0) {$\overline{N}(S')$};
\node at (3,0) {$C'$};
\draw [rotate around = {-45:(2,0)}] (2,0) ellipse (25 pt and 15 pt);
\draw [rotate around = {-45:(1,-0.5)}] (1,-0.5) ellipse  (10 pt and 5 pt);
\draw [rotate  around = {-10:(2.2,1)}] (2.2,1) ellipse  (10 pt and 5 pt);
\draw (2.2,1) -- (1,1);
\draw (1.7,0.3) -- (1, 0.3);
\draw (1.7,0.5) -- (0.5,1);
\draw (0.9,-0.4) -- (0.4, 0.2);
}

\visible<5>{
\node at (1.7,1.2) [robber] {};
}
\visible<6>{
\node at (1.7,0) [robber] {};
}

\end{tikzpicture}
\end{center}
\end{proof}
\end{frame}

\begin{frame}{The Large Component Lemma}
\begin{lemma}
Assume that for every subset $S$ of vertices of size $\leq m$,
$G-\overline{N}(S)$ has a connected component of size $> n/2$.
Then $c_{\infty}(G) > m$.
\end{lemma}
\begin{corollary}
Let $c=c_{\infty}(G)$.
There exists a subset $S$ of size $\leq c$
such that $G-\overline{N}(S)$ has no component of size $> n/2$.
\end{corollary}
\end{frame}

\begin{frame}{Vertex Expansion}
\begin{definition}
Let $G$ be a graph.
The \alert{vertex expansion} of $G$, \alert{$\iota(G)$}, is the following quantity:
$$\iota(G) = \min_{|S| \leq n/2} \frac {|\overline{N}(S)\setminus S|}{|S|}.$$
\end{definition}
\pause
\begin{example}

\begin{center}
\begin{tikzpicture}[thin, scale = 0.5]
        \draw (0,0) -- (-1,1) -- (-1,2) -- (0,3) -- (1,2) -- (1,1) -- (1,2) -- (-1,2) -- (1,1) -- (0,0);
		\node at (0,0) [graphnode]{};
		\node at (-1,1) [graphnode,draw=green!100,fill=green!100]{};
		\node at (-1,2) [graphnode]{};
		\node at (0,3) [graphnode]{};
		\node at (1,2) [graphnode]{};
		\node at (1,1) [graphnode,draw=green!100,fill=green!100]{};
		\node at (1,2) [graphnode]{};
        \draw[dashed](0,2.5) ellipse(50pt and 30pt);
        \node at (-2.3,2.5) {$S_1$};
        \node at (0,-1) {$\iota(G_1) = 2/3$};


\visible<3> {
        \draw (9,1) -- (10,1);
        \draw (10,2) -- (9,2) -- (11,3) -- (11,0) -- (9,1);
		\node at (9,1) [graphnode]{};
		\node at (10,1) [graphnode]{};
		\node at (10,2) [graphnode]{};
		\node at (9,2) [graphnode]{};
		\node at (11,3) [graphnode]{};
		\node at (11,0) [graphnode,draw=green!100,fill=green!100]{};
		\node at (9,2) [graphnode]{};

        \draw[dashed](10,2.5) ellipse(50pt and 30pt);
        \node at (10-2.3,2.5) {$S_2$};

        \node at (10,-1) {$\iota(G_2) = 1/3$};
}
\end{tikzpicture}
\end{center}

\end{example}
%Note: for every $G$, $\iota(G) \leq 1$.
\end{frame}

\begin{frame}{Lower Bound for Expander Graphs}
\begin{theorem}
$$c_{\infty}(G) \geq  \frac{\iota n}{4(\Delta+1)}$$
\end{theorem}
\pause
\begin{proof}
\small
Let $c=c_{\infty}(G)$.
There exists a subset $S$ of size $\leq c$
such that $G-\overline{N}(S)$ has no component of size $> n/2$.
\pause
Clearly $\overline{N}(S) \leq c(\Delta+1)$.
Let $C_1,\dots,C_m$ be the components of $G-\overline{N}(S)$.\\
\only<4>{
If $|C_1|+\dots+|C_m| < n/4$, then $\overline{N}(S) \geq 3n/4$, so $$c(\Delta+1) \geq \frac{3n}{4} > \frac{\iota n}{4}\qedhere$$
}
\visible<5>{
If $|C_1|+\dots+|C_m| \geq n/4$, as each $C_i$ has size $\leq n/2$,
one can pick some of the $C_i$'s such that their union $U$ has $n/4 \leq |U| \leq n/2$.
Set $U$ has at least $\iota |U|$ neighbours outside, so
$$c(\Delta+1) \geq |\overline{N}(S)| \geq \iota |U| \geq \iota n / 4\qedhere$$}
\end{proof}
\end{frame}

\begin{frame}{The {E}rd\"{o}s-R\'{e}nyi Random Graph}
\begin{definition}
Let $n$ be a positive integer and $p$ be a real number in $[0,1]$.
The {E}rd\"{o}s-R\'{e}nyi random graph \alert{$\mathcal{G}(n,p)$}
is a random labelled graph on $n$ vertices
such that each edge appears in $\mathcal{G}(n,p)$ independently and with probability $p$.
For a function $p : \mathbb{N} \rightarrow [0,1]$ and a graph property $A$,
we say $\mathcal{G}(n,p)$ \alert{asymptotically almost surely (a.a.s.)} satisfies $A$,
if we have
$$\lim_{n\rightarrow \infty} \mathbf{Pr} \left[\mathcal{G}(n,p(n))\ \mathrm{satisfies}\ A\right] = 1$$
\end{definition}
\end{frame}

\begin{frame}{Lower Bounds for Random Graphs}
\begin{theorem} [from previous slides]
$$c_{\infty}(G) \geq \iota \frac{n}{4(\Delta+1)}$$
\end{theorem}
\begin{theorem}
If $np \geq 20 \ln n$,
then a.a.s.~$\iota(\mathcal G(n,p)) \geq 10^{-3}$.
\end{theorem}
\pause
\begin{corollary}
If $np \geq 20 \ln n$,
then a.a.s.~$c_{\infty}(\mathcal G(n,p)) = \Omega \left(\frac{1}{p}\right)$.
\end{corollary}
\end{frame}

\begin{frame}{Upper Bounds for Random Graphs}
\begin{corollary}[from previous slides]
If $np \geq 20 \ln n$,
then a.a.s.~$c_{\infty}(\mathcal G(n,p)) = \Omega \left(\frac{1}{p}\right)$.
\end{corollary}
\pause
\begin{theorem}
If $np > 2\ln n$, then a.a.s.~the domination number of $\mathcal G(n,p)$ is $O \left( \frac{\log (np)}{p}\right)$. \hfill [Alon, Spencer'92]
\end{theorem}
\pause
\begin{corollary}
If $np > 2\ln n$, then a.a.s.~$$c_{\infty}(\mathcal G(n,p)) = O\left( \frac{\log (np)}{p}\right)$$
\end{corollary}
\end{frame}

\begin{frame}{Tighter Bounds for Denser Random Graphs}
\begin{theorem}
\begin{itemize}
\item \small If $np = n ^{\alpha + o(1)}$, where $1/2 < \alpha < 1$, then a.a.s~
$$c_{\infty}(\mathcal G(n,p)) = \Theta \left( \frac{\log n}{p}\right)$$
\item \small If $np = n^{1-o(1)}$ then a.a.s~
$$c_{\infty}(\mathcal G(n,p)) = (1+o(1)) \frac{\log n}{\log \frac{1}{1-p}}$$
\end{itemize}
\end{theorem}
\pause
\begin{proof}
\small
Use bounds on domination number for upper bounds,\\
and results for the ``slow robber'' version (proved by Bonato, and Pra{\l}at, and Wang'07)
for the lower bounds.
\end{proof}
\end{frame}



\begin{frame} {Edge Expansion}

\begin{definition}
For $S\subseteq V(G)$, let \alert{$\partial S$} denote the set of edges with exactly one endpoint in $S$.
Then the \alert{edge expansion} of $G$, written \alert{$\iota_e(G)$}, is defined as:
$$\iota_e(G) = \min_{|S| \leq n/2} \frac {|\partial S|}{|S|}$$
\end{definition}
\pause
\begin{example}
\begin{center}
\begin{tikzpicture}[thin, scale = 0.5]
        \draw (0,0) -- (-1,1) -- (-1,2) -- (0,3) -- (1,2) -- (1,1) -- (1,2) -- (-1,2) -- (1,1) -- (0,0);
        \draw [color = green!100, very thick] (-1,1) -- (-1,2);
        \draw [color = green!100, very thick] (1,1) -- (1,2);
        \draw [color = green!100, very thick] (1,1) -- (-1,2);
		\node at (0,0) [graphnode]{};
		\node at (-1,1) [graphnode]{};
		\node at (-1,2) [graphnode]{};
		\node at (0,3) [graphnode]{};
		\node at (1,2) [graphnode]{};
		\node at (1,1) [graphnode]{};
		\node at (1,2) [graphnode]{};
        \draw[dashed](0,2.5) ellipse(50pt and 30pt);
        \node at (-2.3,2.5) {$S_1$};
        \node at (0,-1) {$\iota_e(G_1) = 1$};

\pause
        \draw (9,1) -- (10,1);
        \draw (10,2) -- (9,2) -- (11,3) -- (11,0) -- (9,1);
        \draw [color = green!100, very thick] (11,3) -- (11,0);
		\node at (9,1) [graphnode]{};
		\node at (10,1) [graphnode]{};
		\node at (10,2) [graphnode]{};
		\node at (9,2) [graphnode]{};
		\node at (11,3) [graphnode]{};
		\node at (11,0) [graphnode]{};
		\node at (9,2) [graphnode]{};
        \draw[dashed](10,2.5) ellipse(50pt and 30pt);
        \node at (10-2.3,2.5) {$S_2$};
        \node at (10,-1) {$\iota_e(G_2) = 1/3$};
\end{tikzpicture}
\end{center}
\end{example}

\end{frame}

\begin{frame}{Asymptotic Cop Number of Random Regular Graphs}

\begin{theorem}
$$c_{\infty}(G) \geq \frac{\iota_e n}{2\Delta^2}$$
\end{theorem}
\pause
\begin{corollary}
Fix $d\geq 3$.
With probability $\rightarrow 1$ as $n \rightarrow \infty$,
a random $d$-regular labelled graph $G$ on $n$ vertices has $c_{\infty}(G) = \Theta (n)$.
\end{corollary}
\pause
\begin{proof}
\begin{gather*}
\mathrm{A.a.s.\ }\iota_e(G) \geq d/2 - \sqrt{d\ln 2} \qquad \mathrm{[Bollob\'{a}s'88],\ so} \\
c_{\infty}(G) \geq \frac{d - 2\sqrt{d\ln 2}}{4d^2}\, n \qedhere
\end{gather*}
\end{proof}
\end{frame}

\begin{frame}{Results Not Mentioned Here}
\begin{enumerate}
\item Characterization of graphs with cop number one, $O(n^2)$ algorithm
\item Results on Cartesian products of graphs
\item The same-speed variation
\end{enumerate}
\end{frame}

\section{Open Problems}

\begin{frame}{Open Problems}
\begin{enumerate}
\item [1.] If the robber has finite speed $s$, we proved that there exist graphs with
$$c_s(G) = \Omega\left(n^{s/s+1}\right)$$
We conjecture that this bound is tight, that is,
$$c_s(G) = O\left(n^{s/s+1}\right)$$
This seems to be difficult: even if $s=1$,
the best known upper bound is
$$c_1(G) \leq n^{1-o(1)}$$
\end{enumerate}
\end{frame}

\begin{frame}{Open Problems}
\begin{enumerate}
\item [2.]
We proved that for every $G$,
$$\frac{tw(G) + 1}{\Delta+1} \leq c_{\infty}(G) \leq tw(G) + 1$$
Using this we showed that if $G$ is the $m$-dimensional hypercube with $n=2^m$ vertices, then
$$ \frac{\eta_1 n}{m\sqrt{m}} \leq c_{\infty}(G) \leq \frac{\eta_2 n}{m}$$
Can we eliminate this $\sqrt m$ factor?
\pause
\item [3.] We proved that finding the cop number of an interval graph is 3-approximable.
Is this problem polynomial-time solvable? Does a better approximation algorithm exist?
\end{enumerate}
\end{frame}

\begin{frame}{Open Problems}
\begin{enumerate}
\item [4.] We proved that there are chordal graphs with $c_{\infty}(G) = \Omega(n / \log n)$.
Is this bound tight? Do there exist chordal graphs with $c_{\infty}(G) =\Theta(n)$?
\pause
\item [5.] When $np \geq 20 \ln n$, we proved that a.a.s.
$$ \frac{k_1}{p} \leq c_{\infty}(\mathcal G(n,p)) \leq \frac{k_2 \log (np)}{p}$$
Can we eliminate this $\log (np)$ factor?
\end{enumerate}
\end{frame}

\begin{frame}{Thank You!}
\begin{center}
Any Questions?
\end{center}
\end{frame}


\end{document} 