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.

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.

DOI : https://doi.org/10.1214/10-AIHP407
Classification : 60G50,  05C80,  82B41
Mots clés : random walk, vacant set, regular graph, expanders, random interlacement, phase transition
@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},
     pages = {929--968},
     publisher = {Gauthier-Villars},
     volume = {47},
     number = {4},
     year = {2011},
     doi = {10.1214/10-AIHP407},
     zbl = {1267.05237},
     language = {en},
     url = {www.numdam.org/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) no. 4, pp. 929-968. doi : 10.1214/10-AIHP407. http://www.numdam.org/item/AIHPB_2011__47_4_929_0/

[1] D. J. Aldous and M. Brown. Inequalities for rare events in time-reversible Markov chains. II. Stochastic Process. Appl. 44 (1993) 15-25. | MR 1198660 | Zbl 0812.60054

[2] D. J. Aldous and J. A. Fill. Reversible Markov chains and random walks on graphs. Available at http://www.stat.berkeley.edu/~aldous/RWG/book.html.

[3] N. Alon, I. Benjamini and A. Stacey. Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 (2004) 1727-1745. | MR 2073175 | Zbl 1046.05071

[4] K. B. Athreya. Large deviation rates for branching processes. I. Single type case. Ann. Appl. Probab. 4 (1994) 779-790. | MR 1284985 | Zbl 0806.60068

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

[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] C. Borgs, J. T. Chayes, R. Van Der Hofstad, G. Slade and J. Spencer. 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] A. Broder and E. Shamir. 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] A. Dembo and A.-S. Sznitman. 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] R. Durrett. Probability: Theory and Examples, 2nd edition. Duxbury Press, Belmont, CA, 1996. | MR 1609153 | Zbl 1202.60002

[11] P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960) 17-61. | MR 125031 | Zbl 0103.16301

[12] J. Friedman. On the second eigenvalue and random walks in random d-regular graphs. Combinatorica 11 (1991) 331-362. | MR 1137767 | Zbl 0760.05078

[13] J. Friedman. 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] E. Lubetzky and A. Sly. 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] A. Lubotzky, R. Phillips and P. Sarnak. Ramanujan graphs. Combinatorica 8 (1988) 261-277. | MR 963118 | Zbl 0661.05035

[16] C. Mcdiarmid. 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] A. Nachmias and Y. Peres. Critical percolation on random regular graphs. Random Structures Algorithms 36 (2010) 111-148. Available at arXiv:0707.2839. | MR 2583058 | Zbl 1209.05228

[18] B. Pittel. Edge percolation on a random regular graph of low degree. Ann. Probab. 36 (2008) 1359-1389. | MR 2435852 | Zbl 1160.05054

[19] L. Saloff-Coste. 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] V. Sidoravicius and A.-S. Sznitman. Percolation for the vacant set of random interlacements. Comm. Pure Appl. Math. 62 (2009) 831-858. | MR 2512613 | Zbl 1168.60036

[21] A.-S. Sznitman. 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] A.-S. Sznitman. 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] A.-S. Sznitman. Random walks on discrete cylinders and random interlacements. Probab. Theory Related Fields 145 (2009) 143-174. | MR 2520124 | Zbl 1172.60316

[24] A.-S. Sznitman. Upper bound on the disconnection time of discrete cylinders and random interlacements. Ann. Probab. 37 (2009) 1715-1746. | MR 2561432 | Zbl 1179.60025

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

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

[27] A. Teixeira and D. Windisch. On the fragmentation of a torus by random walk. Commun. Pure Appl. Math. To appear (2011). Available at arXiv:1007.0902. | MR 2838338

[28] D. Windisch. Random walk on a discrete torus and random interlacements. Electron. Commun. Probab. 13 (2008) 140-150. | MR 2386070 | Zbl 1187.60089