Tutte seminar - Nick Wormald

Friday, September 23, 2011 3:30 pm - 4:30 pm EDT (GMT -04:00)

Cops and robber on a random graph

Speaker: Nick Wormald
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158


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 a random d-regular graph, d ≥ 3, as well as in the standard random graph model G(n,p).