Giant vacant component left by a random walk in a random \(d\)-regular graph. (English. French summary) Zbl 1267.05237

The trajectory is considered of a simple random walk on a regular graph of order \(n\) with tree-like structure for increasing \(n\). The vacant set is the complement of the trajectory. Its percolative properties as \(n\) increases are investigated at time \(un\) where \(u\) is a fixed positive parameter. It is shown that there exists a threshold for \(u\) such that the largest component of the vacant set is of order \(n\) below the threshold and of order \(\log(n)\) above the threshold. Connections with the random interlacement model are also given.


05C81 Random walks on graphs
60G50 Sums of independent random variables; random walks
05C80 Random graphs (graph-theoretic aspects)
82B41 Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics
Full Text: DOI arXiv Euclid


[1] D. J. Aldous and M. Brown. Inequalities for rare events in time-reversible Markov chains. II. Stochastic Process. Appl. 44 (1993) 15-25. · Zbl 0812.60054
[2] D. J. Aldous and J. A. Fill. Reversible Markov chains and random walks on graphs. Available at . · Zbl 0513.60068
[3] N. Alon, I. Benjamini and A. Stacey. Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 (2004) 1727-1745. · Zbl 1046.05071
[4] K. B. Athreya. Large deviation rates for branching processes. I. Single type case. Ann. Appl. Probab. 4 (1994) 779-790. · Zbl 0806.60068
[5] K. B. Athreya and P. E. Ney. Branching Processes. Die Grundlehren der Mathematischen Wissenschaften 196 . Springer, New York, 1972. · 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. · 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. · 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. · Zbl 1105.60029
[10] R. Durrett. Probability: Theory and Examples , 2nd edition. Duxbury Press, Belmont, CA, 1996. · Zbl 1202.60001
[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. · Zbl 0103.16301
[12] J. Friedman. On the second eigenvalue and random walks in random d -regular graphs. Combinatorica 11 (1991) 331-362. · 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. · 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 . · Zbl 1202.60012
[15] A. Lubotzky, R. Phillips and P. Sarnak. Ramanujan graphs. Combinatorica 8 (1988) 261-277. · 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. · Zbl 0712.05012
[17] A. Nachmias and Y. Peres. Critical percolation on random regular graphs. Random Structures Algorithms 36 (2010) 111-148. Available at . · Zbl 1209.05228
[18] B. Pittel. Edge percolation on a random regular graph of low degree. Ann. Probab. 36 (2008) 1359-1389. · 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. · 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. · 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). · Zbl 1210.60047
[22] A.-S. Sznitman. On the domination of random walk on a discrete cylinder by random interlacements. Electron. J. Probab. 14 (2009) 1670-1704. · Zbl 1196.60170
[23] A.-S. Sznitman. Random walks on discrete cylinders and random interlacements. Probab. Theory Related Fields 145 (2009) 143-174. · 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. · Zbl 1179.60025
[25] A.-S. Sznitman. Vacant set of random interlacements and percolation. Ann. of Math. (2) 171 (2010) 2039-2087. · Zbl 1202.60160
[26] A. Teixeira. Interlacement percolation on transient weighted graphs. Electron. J. Probab. 14 (2009) 1604-1628. · 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 . · Zbl 1235.60143
[28] D. Windisch. Random walk on a discrete torus and random interlacements. Electron. Commun. Probab. 13 (2008) 140-150. · Zbl 1187.60089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.