Tutte seminar - Nick Wormald

Cops and robber on a random graph

Abstract:

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is Meyniel's, which asserts that for some absolute constant C, the cop number of every graph G is at most C|V(G)|. We show that Meyniel's conjecture holds asymptotically almost surely for G a random d-regular graph, d ≥ 3, as well as in the standard random graph model G(n,p).