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.

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).

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).

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

[1] D. J. Aldous and M. Brown. Inequalities for rare events in time-reversible Markov chains. I. In Stochastic Inequalities (Seattle, WA, 1991) 1–16. IMS Lecture Notes Monogr. Ser. 22. IMS, Hayward, CA, 1992. | MR | Zbl

[2] D. J. Aldous and J. A. Fill. Reversible Markov Chains and Random Walks on Graphs. Book in preparation. Available at http://www.stat.berkeley.edu/users/aldous/RWG/book.html.

[3] R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, 1979) 218–223. IEEE, New York, 1979. | MR

[4] K. B. Athreya and P. E. Ney. Branching Processes. Die Grundlehren der mathematischen Wissenschaften 196. Springer, New York, 1972. | MR | Zbl

[5] I. Benjamini, G. Kozma and N. Wormald. The mixing time of the giant component of a random graph, 2006. Available at arXiv:math/0610459. | MR | Zbl

[6] I. Benjamini and A.-S. Sznitman. Giant component and vacant set for random walk on a discrete torus. J. Eur. Math. Soc. (JEMS) 10 (2008) 133–172. | MR | Zbl

[7] B. Bollobás. Random Graphs, 2nd edition. Cambridge Studies in Advanced Mathematics 73. Cambridge Univ. Press, Cambridge, 2001. | DOI | MR | Zbl

[8] J. Černý, A. Teixeira and D. Windisch. Giant vacant component left by a random walk in a random $d$-regular graph. Ann. Inst. Henri Poincaré Probab. Stat. 47 (2011) 929–968. | DOI | Numdam | MR | Zbl

[9] J. Černý and A. Q. Teixeira. From Random Walk Trajectories to Random Interlacements. Mathematical Surveys 23. Sociedade Brasileira de Matemática, Rio de Janeiro, 2012. | MR | Zbl

[10] J. Černý and A. Teixeira. Critical window for the vacant set left by random walk on random regular graphs. Random Structures Algorithms 43 (2013) 313–337. | DOI | MR | Zbl

[11] C. Cooper and A. Frieze. Component structure of the vacant set induced by a random walk on a random graph. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms 1211–1221. SIAM, Philadelphia, PA, 2011. | MR | Zbl

[12] R. Durrett. Random Graph Dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge Univ. Press, Cambridge, 2010. | MR | Zbl

[13] P. Erdős and A. Rényi. On the evolution of random graphs. Bull. Inst. Internat. Statist. 38 (1961) 343–347. | MR | Zbl

[14] H. Hatami and M. Molloy. The scaling window for a random graph with a given degree sequence. Random Structures Algorithms 41 (2012) 99–123. | DOI | MR | Zbl

[15] R. V. D. Hofstad. Random graphs and complex networks. Lecture notes in preparation, 2008. Available at http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf.

[16] S. Janson, T. Luczak and A. Rucinski. Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, New York, 2000. | DOI | MR | Zbl

[17] M. Jara, C. Landim and A. Teixeira. Universality of trap models in the ergodic time scale. Ann. Probab. 42 (2014) 2497–2557. | DOI | MR | Zbl

[18] D. A. Levin, Y. Peres and E. L. Wilmer. Markov Chains and Mixing Times. Amer. Math. Soc., Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. | MR | Zbl

[19] R. Lyons and Y. Peres. Probability on Trees and Networks. Cambridge Univ. Press, Cambridge, in preparation, 2015. Current version available at http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html.

[20] C. Mcdiarmid. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms Combin. 16. 195–248. Springer, Berlin, 1998. | MR | Zbl

[21] A.-S. Sznitman. Vacant set of random interlacements and percolation. Ann. of Math. (2) 171 (2010) 2039–2087. | MR | Zbl

[22] M. Tassy. Random interlacements on Galton–Watson trees. Electron. Commun. Probab. 15 (2010) 562–571. | DOI | MR | Zbl

[23] A. Teixeira. Interlacement percolation on transient weighted graphs. Electron. J. Probab. 14 (54) (2009) 1604–1628. | MR | Zbl

[24] A. Teixeira and D. Windisch. On the fragmentation of a torus by random walk. Comm. Pure Appl. Math. 64 (2011) 1599–1646. | DOI | MR | Zbl