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.
@article{AIHPB_2011__47_4_929_0,
author = {\v Cern\'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},
volume = {47},
year = {2011},
pages = {929-968},
doi = {10.1214/10-AIHP407},
zbl = {1267.05237},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 929-968. doi : 10.1214/10-AIHP407. http://gdmltest.u-ga.fr/item/AIHPB_2011__47_4_929_0/
[1] and . Inequalities for rare events in time-reversible Markov chains. II. Stochastic Process. Appl. 44 (1993) 15-25. | MR 1198660 | Zbl 0812.60054
[2] and . Reversible Markov chains and random walks on graphs. Available at http://www.stat.berkeley.edu/~aldous/RWG/book.html.
[3] , and . Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 (2004) 1727-1745. | MR 2073175 | Zbl 1046.05071
[4] . Large deviation rates for branching processes. I. Single type case. Ann. Appl. Probab. 4 (1994) 779-790. | MR 1284985 | Zbl 0806.60068
[5] and . Branching Processes. Die Grundlehren der Mathematischen Wissenschaften 196. Springer, New York, 1972. | MR 373040 | Zbl 0259.60002
[6] and . 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] , , , and . Random subgraphs of finite graphs. I. The scaling window under the triangle condition. Random Structures Algorithms 27 (2005) 137-184. | MR 2155704 | Zbl 1076.05071
[8] and . 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.
[9] and . On the disconnection of a discrete cylinder by a random walk. Probab. Theory Related Fields 136 (2006) 321-340. | MR 2240791 | Zbl 1105.60029
[10] . Probability: Theory and Examples, 2nd edition. Duxbury Press, Belmont, CA, 1996. | MR 1609153 | Zbl 1202.60002
[11] and . On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960) 17-61. | MR 125031 | Zbl 0103.16301
[12] . On the second eigenvalue and random walks in random d-regular graphs. Combinatorica 11 (1991) 331-362. | MR 1137767 | Zbl 0760.05078
[13] . A proof of Alon's second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc. 195 (2008) viii+100. | MR 2437174 | Zbl 1177.05070
[14] and . Cutoff phenomena for random walks on random regular graphs. Duke Math. J. 153 (2010) 475-510. Available at arXiv:0812.0060. | MR 2667423 | Zbl 1202.60012
[15] , and . Ramanujan graphs. Combinatorica 8 (1988) 261-277. | MR 963118 | Zbl 0661.05035
[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 1036755 | Zbl 0712.05012
[17] and . Critical percolation on random regular graphs. Random Structures Algorithms 36 (2010) 111-148. Available at arXiv:0707.2839. | MR 2583058 | Zbl 1209.05228
[18] . Edge percolation on a random regular graph of low degree. Ann. Probab. 36 (2008) 1359-1389. | MR 2435852 | Zbl 1160.05054
[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 1490046 | Zbl 0885.60061
[20] and . Percolation for the vacant set of random interlacements. Comm. Pure Appl. Math. 62 (2009) 831-858. | MR 2512613 | Zbl 1168.60036
[21] . A lower bound on the critical parameter of interlacement percolation in high dimension. Probab. Theory Related Fields. To appear (2011). | MR 2778797 | Zbl pre05950541
[22] . On the domination of random walk on a discrete cylinder by random interlacements. Electron. J. Probab. 14 (2009) 1670-1704. | MR 2525107 | Zbl 1196.60170
[23] . Random walks on discrete cylinders and random interlacements. Probab. Theory Related Fields 145 (2009) 143-174. | MR 2520124 | Zbl 1172.60316
[24] . Upper bound on the disconnection time of discrete cylinders and random interlacements. Ann. Probab. 37 (2009) 1715-1746. | MR 2561432 | Zbl 1179.60025
[25] . Vacant set of random interlacements and percolation. Ann. of Math. (2) 171 (2010) 2039-2087. | MR 2680403 | Zbl 1202.60160
[26] . Interlacement percolation on transient weighted graphs. Electron. J. Probab. 14 (2009) 1604-1628. | MR 2525105 | Zbl 1192.60108
[27] and . On the fragmentation of a torus by random walk. Commun. Pure Appl. Math. To appear (2011). Available at arXiv:1007.0902. | MR 2838338
[28] . Random walk on a discrete torus and random interlacements. Electron. Commun. Probab. 13 (2008) 140-150. | MR 2386070 | Zbl 1187.60089