Nous étudions la marche aléatoire sur la composante principale d’un graphe aléatoire d’Erdős–Rényi avec sommets, en particulier l’ensemble vacant au niveau , le complément de la trajectoire de la marche aléatoire jusqu’à un moment proportionnel à et . Nous prouvons que la structure de composant montre une transition de phase à un valeur critique : Pour l’ensemble vacant se compose, avec une forte probabilité quand croît, d’une seule composante principale avec volume d’ordre et des composantes petites d’ordre au plus , alors que pour tous les composants sont petits. En outre nous montrons que 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 vertices, in particular the so-called vacant set at level , the complement of the trajectory of the random walk run up to a time proportional to and . We show that the component structure of the vacant set exhibits a phase transition at a critical parameter : For the vacant set has with high probability a unique giant component of order and all other components small, of order at most , whereas for it has with high probability all components small. Moreover, we show that 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).
Mots clés : random walk, vacant set, Erdős–Rényi random graph, giant component, phase transition, random interlacements
@article{AIHPB_2015__51_2_756_0, author = {Wassmer, Tobias}, title = {Phase transition for the vacant set left by random walk on the giant component of a random graph}, journal = {Annales de l'I.H.P. Probabilit\'es et statistiques}, pages = {756--780}, publisher = {Gauthier-Villars}, volume = {51}, number = {2}, year = {2015}, doi = {10.1214/13-AIHP596}, mrnumber = {3335024}, zbl = {1312.05126}, language = {en}, url = {http://www.numdam.org/articles/10.1214/13-AIHP596/} }
TY - JOUR AU - Wassmer, Tobias TI - Phase transition for the vacant set left by random walk on the giant component of a random graph JO - Annales de l'I.H.P. Probabilités et statistiques PY - 2015 SP - 756 EP - 780 VL - 51 IS - 2 PB - Gauthier-Villars UR - http://www.numdam.org/articles/10.1214/13-AIHP596/ DO - 10.1214/13-AIHP596 LA - en ID - AIHPB_2015__51_2_756_0 ER -
%0 Journal Article %A Wassmer, Tobias %T Phase transition for the vacant set left by random walk on the giant component of a random graph %J Annales de l'I.H.P. Probabilités et statistiques %D 2015 %P 756-780 %V 51 %N 2 %I Gauthier-Villars %U http://www.numdam.org/articles/10.1214/13-AIHP596/ %R 10.1214/13-AIHP596 %G en %F AIHPB_2015__51_2_756_0
Wassmer, Tobias. Phase transition for the vacant set left by random walk on the giant component of a random graph. Annales de l'I.H.P. Probabilités et statistiques, Tome 51 (2015) no. 2, pp. 756-780. doi : 10.1214/13-AIHP596. http://www.numdam.org/articles/10.1214/13-AIHP596/
[1] 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
and .[2] Reversible Markov Chains and Random Walks on Graphs. Book in preparation. Available at http://www.stat.berkeley.edu/users/aldous/RWG/book.html.
and .[3] 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
, , , and .[4] Branching Processes. Die Grundlehren der mathematischen Wissenschaften 196. Springer, New York, 1972. | MR | Zbl
and .[5] The mixing time of the giant component of a random graph, 2006. Available at arXiv:math/0610459. | MR | Zbl
, and .[6] Giant component and vacant set for random walk on a discrete torus. J. Eur. Math. Soc. (JEMS) 10 (2008) 133–172. | MR | Zbl
and .[7] Random Graphs, 2nd edition. Cambridge Studies in Advanced Mathematics 73. Cambridge Univ. Press, Cambridge, 2001. | DOI | MR | Zbl
.[8] Giant vacant component left by a random walk in a random -regular graph. Ann. Inst. Henri Poincaré Probab. Stat. 47 (2011) 929–968. | DOI | Numdam | MR | Zbl
, and .[9] From Random Walk Trajectories to Random Interlacements. Mathematical Surveys 23. Sociedade Brasileira de Matemática, Rio de Janeiro, 2012. | MR | Zbl
and .[10] Critical window for the vacant set left by random walk on random regular graphs. Random Structures Algorithms 43 (2013) 313–337. | DOI | MR | Zbl
and .[11] 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
and .[12] Random Graph Dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge Univ. Press, Cambridge, 2010. | MR | Zbl
.[13] On the evolution of random graphs. Bull. Inst. Internat. Statist. 38 (1961) 343–347. | MR | Zbl
and .[14] The scaling window for a random graph with a given degree sequence. Random Structures Algorithms 41 (2012) 99–123. | DOI | MR | Zbl
and .[15] Random graphs and complex networks. Lecture notes in preparation, 2008. Available at http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf.
.[16] Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, New York, 2000. | DOI | MR | Zbl
, and .[17] Universality of trap models in the ergodic time scale. Ann. Probab. 42 (2014) 2497–2557. | DOI | MR | Zbl
, and .[18] Markov Chains and Mixing Times. Amer. Math. Soc., Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. | MR | Zbl
, and .[19] Probability on Trees and Networks. Cambridge Univ. Press, Cambridge, in preparation, 2015. Current version available at http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html.
and .[20] Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms Combin. 16. 195–248. Springer, Berlin, 1998. | MR | Zbl
.[21] Vacant set of random interlacements and percolation. Ann. of Math. (2) 171 (2010) 2039–2087. | MR | Zbl
.[22] Random interlacements on Galton–Watson trees. Electron. Commun. Probab. 15 (2010) 562–571. | DOI | MR | Zbl
.[23] Interlacement percolation on transient weighted graphs. Electron. J. Probab. 14 (54) (2009) 1604–1628. | MR | Zbl
.[24] On the fragmentation of a torus by random walk. Comm. Pure Appl. Math. 64 (2011) 1599–1646. | DOI | MR | Zbl
and .Cité par Sources :