Giant vacant component left by a random walk in a random $d$-regular graph

Černý, Jiří; Teixeira, Augusto; Windisch, David

Annales de l'I.H.P. Probabilités et statistiques, Volume 47 (2011) no. 4, pp. 929-968.

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.

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.

Classification: 60G50, 05C80, 82B41
Keywords: random walk, vacant set, regular graph, expanders, random interlacement, phase transition

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

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

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

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

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

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

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

[10] R. Durrett. Probability: Theory and Examples, 2nd edition. Duxbury Press, Belmont, CA, 1996. | MR | Zbl

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

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

[13] J. Friedman. A proof of Alon's second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc. 195 (2008) viii+100. | MR | Zbl

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

[15] A. Lubotzky, R. Phillips and P. Sarnak. Ramanujan graphs. Combinatorica 8 (1988) 261-277. | MR | Zbl

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

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

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

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

[20] V. Sidoravicius and A.-S. Sznitman. Percolation for the vacant set of random interlacements. Comm. Pure Appl. Math. 62 (2009) 831-858. | MR | Zbl

[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

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

[23] A.-S. Sznitman. Random walks on discrete cylinders and random interlacements. Probab. Theory Related Fields 145 (2009) 143-174. | MR | Zbl

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

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

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

[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

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