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

作者：Wassmer Tobias^*

来源：Annales de l Institut Henri Poincare-Probabilites et Statistiques, 2015, 51(2): 756-780.

DOI：10.1214/13-AIHP596

• Random walk
• Vacant set
• Erdos-Renyi random graph
• Giant component
• Phase transition
• Random interlacements

We study the simple random walk on the giant component of a supercritical Erdos-Renyi 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(star): For u < u(star) the vacant set has with high probability a unique giant component of order n and all other components small, of order at most log(7) n, whereas for u > u(star) it has with high probability all components small. Moreover, we show that u(star) coincides with the critical parameter of random interlacements on a Poisson-Galton-Watson tree, which was identified in (Electron. Commun. Probab. 15 (2010) 562-571).

• 出版日期2015-5