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 |
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).