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

<p>We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(<em>t</em>) be the subgraph induced by the vacant set of the walk at step <em>t</em>. We show that for random graphs <em>G</em>_{<em>n</em>,<em>p</em>} (above the connectivity threshold) and for random regular graphs <em>G</em>_<em>r</em>,<em>r</em> ≥ 3, the graph Γ(<em>t</em>) undergoes a phase transition in the sense of the well-known ErdJW-RSAT1100590x.png -Renyi phase transition. Thus for <em>t</em> ≤ (1 - <em>ε</em>)<em>t</em>^*, there is a unique giant component, plus components of size <em>O</em>(log <em>n</em>), and for <em>t</em> ≥ (1 + <em>ε</em>)<em>t</em>^* all components are of size <em>O</em>(log <em>n</em>). For <em>G</em>_{<em>n</em>,<em>p</em>} and <em>G</em>_<em>r</em> we give the value of <em>t</em>^*, and the size of Γ(<em>t</em>). For <em>G</em>_<em>r</em>, we also give the degree sequence of Γ(<em>t</em>), the size of the giant component (if any) of Γ(<em>t</em>) and the number of tree components of Γ(<em>t</em>) of a given size <em>k</em> = <em>O</em>(log<em>n</em>). We also show that for random digraphs <em>D</em>_{<em>n</em>,<em>p</em>} above the strong connectivity threshold, there is a similar directed phase transition. Thus for<em>t</em> ≤ (1 - <em>ε</em>)<em>t</em>^*, there is a unique strongly connected giant component, plus strongly connected components of size <em>O</em>(log <em>n</em>), and for <em>t</em> ≥ (1 + <em>ε</em>)<em>t</em>^*all strongly connected components are of size <em>O</em>(log <em>n</em>).</p>