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, 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.

[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