Phase transition for the vacant set left by random walk on the giant component of a random graph

2013/08/12 by Wassmer, Tobias
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1308.2548

Abstract

We study the simple random walk on the giant component of a supercritical Erdős-Rényi random graph on n vertices, in particular the so-called vacant set at level u, the complement of the trajectory of the random walk run up to a time proportional to u and n. We show that the component structure of the vacant set exhibits a phase transition at a critical parameter u_⋆: For uu_⋆ it has with high probability all components small. Moreover, we show that u_⋆ coincides with the critical parameter of random interlacements on a Poisson-Galton-Watson tree, which was identified in [Tas10].

Related

• Component structure of the vacant set induced by a random walk on a random graph
• Critical window for the vacant set left by random walk on random regular graphs
• The phase transition in random graphs - a simple proof
• Phase transition for the vacant set of random walk and random interlacements
• Critical random hypergraphs: The emergence of a giant set of identifiable vertices