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), p. 756-780 / Harvested from Numdam

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_{\star }$ : Pour $u<u_{\star }$ 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_{\star }$ tous les composants sont petits. En outre nous montrons que $u_{\star }$ 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).

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_{\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).

Détail

Publié le : 2015-01-01

MR 3335024

DOI : https://doi.org/10.1214/13-AIHP596
Classification:  05C81,  05C08,  60J10,  60K35

Bibliographie

[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 1228050 | Zbl 0812.60054

[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 598110

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

[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 3252922 | Zbl 06370216

[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 2349899 | Zbl 1141.60057

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

[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. | Numdam | MR 2884219 | Zbl 1267.05237

[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 3014964 | Zbl 1269.60002

[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. | MR 3094422 | Zbl 1273.05209

[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 2858394 | Zbl 1259.05155

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

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

[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. | MR 2943428 | Zbl 1247.05218

[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. | MR 1782847 | Zbl 0968.05003

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

[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 2466937 | Zbl 1160.60001

[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 1678578 | Zbl 0927.60027

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

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

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

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