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

Wassmer, Tobias

Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015) no. 2, pp. 756-780

Abstract (VO)

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 $u<u_{☆}$ 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_{☆}$ 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 (Electron. Commun. Probab. 15 (2010) 562–571).

Résumé

Nous étudions la marche aléatoire sur la composante principale d’un graphe aléatoire d’Erdős–Rényi avec $n$ sommets, en particulier l’ensemble vacant au niveau $u$, le complément de la trajectoire de la marche aléatoire jusqu’à un moment proportionnel à $u$ et $n$. Nous prouvons que la structure de composant montre une transition de phase à un valeur critique $u_{☆}$ : Pour $u<u_{☆}$ l’ensemble vacant se compose, avec une forte probabilité quand $n$ croît, d’une seule composante principale avec volume d’ordre $n$ et des composantes petites d’ordre au plus ${log}^{7}n$, alors que pour $u>u_{☆}$ tous les composants sont petits. En outre nous montrons que $u_{☆}$ coïncide avec le paramètre critique des entrelacs aléatoires sur un arbre de Poisson–Galton–Watson identifié en (Electron. Commun. Probab. 15 (2010) 562–571).

Détail

DOI : 10.1214/13-AIHP596

Classification : 05C81, 05C08, 60J10, 60K35
Keywords: random walk, vacant set, Erdős–Rényi random graph, giant component, phase transition, random interlacements