Component structure of the vacant set induced by a random walk on a random graph. Issue 2 (8th February 2012)

• Record Type: Journal Article
• Authors: Cooper, Colin; Frieze, Alan
• Is Part Of: Random structures & algorithms. Volume 42:Issue 2(2013)
• Page Start: 135
• Page End: 158
• Publication Date: 2012-02-08
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20402
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <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 Γ(<italic>t</italic>) be the subgraph induced by the vacant set of the walk at step <italic>t</italic>. We show that for random graphs <italic>G</italic><sub><italic>n</italic>, <italic>p</italic></sub> (above the connectivity threshold) and for random regular graphs <italic>G</italic><sub><italic>r</italic></sub>, <italic>r</italic> ≥ 3, the graph Γ(<italic>t</italic>) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for <italic>t</italic> ≤ (1 ‐ <italic>ε</italic>)<italic>t</italic><sup>*</sup>, there is a unique giant component, plus components of size <italic>O</italic>(log <italic>n</italic>), and for <italic>t</italic> ≥ (1 + <italic>ε</italic>)<italic>t</italic><sup>*</sup> all components are of size <italic>O</italic>(log <italic>n</italic>). For <italic>G</italic><sub><italic>n</italic>, <italic>p</italic></sub> and <italic>G</italic><sub><italic>r</italic></sub> we give the value of <italic>t</italic><sup>*</sup>, and the size of Γ(<italic>t</italic>). For <italic>G</italic><sub><italic>r</italic></sub>, we also give the degree sequence of Γ(<italic>t</italic>), the size of the giant component (if any) of Γ(<italic>t</italic>) and the number of tree components of Γ(<italic>t</italic>) of a given size <italic>k</italic> = <italic>O</italic>(log <italic>n</italic>). We also show that for random digraphs <italic>D</italic><sub><italic>n</italic>, <italic>p</italic></sub> above the strong connectivity threshold, there is a similar directed phase transition. Thus for <italic>t</italic> ≤ (1 ‐ <italic>ε</italic>)<italic>t</italic><sup>*</sup>, there is a unique strongly connected giant component, plus strongly connected components of size <italic>O</italic>(log <italic>n</italic>), and for <italic>t</italic> ≥ (1 + <italic>ε</italic>)<italic>t</italic><sup>*</sup> all strongly connected components are of size <italic>O</italic>(log <italic>n</italic>). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012</p> </abstract>