Component structure of the vacant set induced by a random walk on a random graph

Component structure of the vacant set induced by a random walk on a random graph

Tue, 31/05/2011
14:30 		Colin Cooper (King's College London) Combinatorial Theory Seminar Add to calendar L3
Component structure of the vacant set induced by a random walk on a random graph
We consider random walks on two classes of random graphs and explore the likely structure of the the set of unvisited vertices or vacant set. In both cases, the size of the vacant set $ N(t) $ can be obtained explicitly as a function of $ t $. Let $ \Gamma(t) $ be the subgraph induced by the vacant set. We show that, for random graphs $ G_{n,p} $ above the connectivity threshold, and for random regular graphs $ G_r $, for constant $ r\geq 3 $, there is a phase transition in the sense of the well-known Erdos-Renyi phase transition. Thus for $ t\leq (1-\epsilon)t^* $ we have a unique giant plus components of  size $ O(\log n) $ and for $ t\geq (1+\epsilon)t^* $ we have only components of  size $ O(\log n) $. In the case of $ G_r $ we describe the likely degree sequence, size of the giant component and structure of the small ($ O(\log n) $) size components.