Nous étudions la trajectoire d'une marche aléatoire simple sur un graphe d-régulier avec d ≥ 3 dont la structure ressemble localement à un arbre, quand le nombre de sommets n du graphe croît. Des exemples de tels graphes comprennent des graphes aléatoires d-réguliers et des ‘expanseur de grande maille'. Pour ces graphes, nous étudions les propriétés de percolation de l'ensemble des sommets non visités par la marche jusqu'au moment un, où u > 0 est un paramètre positif fixé. Nous montrons que cet ensemble vacant subit une transition de phase en u dans le sens suivant : il existe un seuil u⋆ ∈ (0, ∞) explicitement calculable tel que, avec une forte probabilité quand n croît, si u < u⋆, la plus grande composante de l'ensemble vacant a un volume d'ordre n, et si u > u⋆, elle a un volume d'ordre logn. La valeur critique u⋆ coïncide avec l'intensité critique des entrelacs aléatoires sur un arbre d-régulier. Nous montrons aussi que les entrelacs aléatoires décrivent bien la structure de l'ensemble vacant dans des voisinages locaux.
We study the trajectory of a simple random walk on a d-regular graph with d ≥ 3 and locally tree-like structure as the number n of vertices grows. Examples of such graphs include random d-regular graphs and large girth expanders. For these graphs, we investigate percolative properties of the set of vertices not visited by the walk until time un, where u > 0 is a fixed positive parameter. We show that this so-called vacant set exhibits a phase transition in u in the following sense: there exists an explicitly computable threshold u⋆ ∈ (0, ∞) such that, with high probability as n grows, if u < u⋆, then the largest component of the vacant set has a volume of order n, and if u > u⋆, then it has a volume of order logn. The critical value u⋆ coincides with the critical intensity of a random interlacement process on a d-regular tree. We also show that the random interlacements model describes the structure of the vacant set in local neighbourhoods.
Mots clés : random walk, vacant set, regular graph, expanders, random interlacement, phase transition
@article{AIHPB_2011__47_4_929_0, author = {\v{C}ern\'y, Ji\v{r}{\'\i} and Teixeira, Augusto and Windisch, David}, title = {Giant vacant component left by a random walk in a random $d$-regular graph}, journal = {Annales de l'I.H.P. Probabilit\'es et statistiques}, pages = {929--968}, publisher = {Gauthier-Villars}, volume = {47}, number = {4}, year = {2011}, doi = {10.1214/10-AIHP407}, zbl = {1267.05237}, language = {en}, url = {http://www.numdam.org/articles/10.1214/10-AIHP407/} }
TY - JOUR AU - Černý, Jiří AU - Teixeira, Augusto AU - Windisch, David TI - Giant vacant component left by a random walk in a random $d$-regular graph JO - Annales de l'I.H.P. Probabilités et statistiques PY - 2011 SP - 929 EP - 968 VL - 47 IS - 4 PB - Gauthier-Villars UR - http://www.numdam.org/articles/10.1214/10-AIHP407/ DO - 10.1214/10-AIHP407 LA - en ID - AIHPB_2011__47_4_929_0 ER -
%0 Journal Article %A Černý, Jiří %A Teixeira, Augusto %A Windisch, David %T Giant vacant component left by a random walk in a random $d$-regular graph %J Annales de l'I.H.P. Probabilités et statistiques %D 2011 %P 929-968 %V 47 %N 4 %I Gauthier-Villars %U http://www.numdam.org/articles/10.1214/10-AIHP407/ %R 10.1214/10-AIHP407 %G en %F AIHPB_2011__47_4_929_0
Černý, Jiří; Teixeira, Augusto; Windisch, David. Giant vacant component left by a random walk in a random $d$-regular graph. Annales de l'I.H.P. Probabilités et statistiques, Tome 47 (2011) no. 4, pp. 929-968. doi : 10.1214/10-AIHP407. http://www.numdam.org/articles/10.1214/10-AIHP407/
[1] Inequalities for rare events in time-reversible Markov chains. II. Stochastic Process. Appl. 44 (1993) 15-25. | MR | Zbl
and .[2] Reversible Markov chains and random walks on graphs. Available at http://www.stat.berkeley.edu/~aldous/RWG/book.html.
and .[3] Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 (2004) 1727-1745. | MR | Zbl
, and .[4] Large deviation rates for branching processes. I. Single type case. Ann. Appl. Probab. 4 (1994) 779-790. | MR | Zbl
.[5] Branching Processes. Die Grundlehren der Mathematischen Wissenschaften 196. Springer, New York, 1972. | 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 subgraphs of finite graphs. I. The scaling window under the triangle condition. Random Structures Algorithms 27 (2005) 137-184. | MR | Zbl
, , , and .[8] On the second eigenvalue of random regular graphs. In 28th Annual Symposium on Foundations of Computer Science 286-294. IEEE Comput. Soc. Press, Washington, DC, 1987.
and .[9] On the disconnection of a discrete cylinder by a random walk. Probab. Theory Related Fields 136 (2006) 321-340. | MR | Zbl
and .[10] Probability: Theory and Examples, 2nd edition. Duxbury Press, Belmont, CA, 1996. | MR | Zbl
.[11] On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960) 17-61. | MR | Zbl
and .[12] On the second eigenvalue and random walks in random d-regular graphs. Combinatorica 11 (1991) 331-362. | MR | Zbl
.[13] A proof of Alon's second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc. 195 (2008) viii+100. | MR | Zbl
.[14] Cutoff phenomena for random walks on random regular graphs. Duke Math. J. 153 (2010) 475-510. Available at arXiv:0812.0060. | MR | Zbl
and .[15] Ramanujan graphs. Combinatorica 8 (1988) 261-277. | MR | Zbl
, and .[16] On the method of bounded differences. In Surveys in Combinatorics, 1989 (Norwich, 1989) 148-188. London Math. Soc. Lecture Note Ser. 141. Cambridge Univ. Press, Cambridge, 1989. | MR | Zbl
.[17] Critical percolation on random regular graphs. Random Structures Algorithms 36 (2010) 111-148. Available at arXiv:0707.2839. | MR | Zbl
and .[18] Edge percolation on a random regular graph of low degree. Ann. Probab. 36 (2008) 1359-1389. | MR | Zbl
.[19] Lectures on finite Markov chains. In Lectures on Probability Theory and Statistics (Saint-Flour, 1996) 301-413. Lecture Notes in Math. 1665. Springer, Berlin, 1997. | MR | Zbl
.[20] Percolation for the vacant set of random interlacements. Comm. Pure Appl. Math. 62 (2009) 831-858. | MR | Zbl
and .[21] A lower bound on the critical parameter of interlacement percolation in high dimension. Probab. Theory Related Fields. To appear (2011). | MR
.[22] On the domination of random walk on a discrete cylinder by random interlacements. Electron. J. Probab. 14 (2009) 1670-1704. | MR | Zbl
.[23] Random walks on discrete cylinders and random interlacements. Probab. Theory Related Fields 145 (2009) 143-174. | MR | Zbl
.[24] Upper bound on the disconnection time of discrete cylinders and random interlacements. Ann. Probab. 37 (2009) 1715-1746. | MR | Zbl
.[25] Vacant set of random interlacements and percolation. Ann. of Math. (2) 171 (2010) 2039-2087. | MR | Zbl
.[26] Interlacement percolation on transient weighted graphs. Electron. J. Probab. 14 (2009) 1604-1628. | MR | Zbl
.[27] On the fragmentation of a torus by random walk. Commun. Pure Appl. Math. To appear (2011). Available at arXiv:1007.0902. | MR
and .[28] Random walk on a discrete torus and random interlacements. Electron. Commun. Probab. 13 (2008) 140-150. | MR | Zbl
.Cité par Sources :