Meyniel's conjecture holds for random graphs

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 the one of Meyniel, which asserts that for some absolute constant C , the cop number of every connected graph G is at most C | V ( G ) |. In this paper, we show that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph G ( n , p ) , which improves upon existing results showing that asymptotically almost surely the cop number of G ( n , p ) is O ( n log n ) provided that p n ≥ ( 2 + ε ) log n for some ε > 0 . We do this by first showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. This will also be used in a separate paper on random d ‐regular graphs, where we show that the conjecture holds asymptotically almost surely when d = d ( n ) ≥ 3 . © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 396–421, 2016