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 `cop-number' 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 cop-number 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 cop-number has order of magnitude $\Omega(n^{1/2+o(1)})$. Joint work with Bela Bollobas and Imre Leader.