
Discrete Mathematics and Optimization Seminar

May. 11th, 2009 MC 320  4:30 PM
Cops and robbers in random graphs
Gabor Kun
Institue for Advanced Study.

We will study the following game known as cops and robbers. There is a
finite, connected, undirected graph $G$, and $m$ cops and one robber. At
the start, each cop chooses one vertex, and then the robber makes his
choice of a vertex. Then they move alternately (first the cops then the
robber). In the cops' turn, each cop may move to an adjacent vertex, or
remain where he is, and similarly for the robber. The cops win the game
if one of the cops catches the robber, i.e. lands on the same vertex. We
denote by $c(G)$ the `copnumber' of $G$, meaning the minimal $m$ such
that $m$ cops have a winning strategy in $G$, and by $c(n)$ the maximum
of $c(G)$ over all graphs with $n$ vertices. Maamoun and Meyniel
determined the copnumber for grids. Aigner and Fromme proved that in
the case of planar graphs three cops can catch the robber. Frankl gave
lower bounds on $c(G)$ in the case of large girth graphs. Meyniel
conjectured that $c(n)=O(\sqrt{n})$. Our main aim is to prove that the
conjecture essentially holds for sparse random graphs: in this case the
copnumber has order of magnitude $\Omega(n^{1/2+o(1)})$. Joint work
with Bela Bollobas and Imre Leader.



