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

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

Annales de l'I.H.P. Probabilités et statistiques (2011)

  • Volume: 47, Issue: 4, page 929-968
  • ISSN: 0246-0203

Abstract

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

How to cite

top

Černý, Jiří, Teixeira, Augusto, and 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 47.4 (2011): 929-968. <http://eudml.org/doc/243363>.

@article{Černý2011,
abstract = {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 &gt; 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 &lt; u⋆, then the largest component of the vacant set has a volume of order n, and if u &gt; 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.},
author = {Černý, Jiří, Teixeira, Augusto, Windisch, David},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {random walk; vacant set; regular graph; expanders; random interlacement; phase transition; simple random walk; trajectory; random interlacement model; fixed positive parameter; largest component; percolative properties; tree-like structure; threshold},
language = {eng},
number = {4},
pages = {929-968},
publisher = {Gauthier-Villars},
title = {Giant vacant component left by a random walk in a random d-regular graph},
url = {http://eudml.org/doc/243363},
volume = {47},
year = {2011},
}

TY - JOUR
AU - Černý, Jiří
AU - Teixeira, Augusto
AU - Windisch, David
TI - Giant vacant component left by a random walk in a random d-regular graph
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2011
PB - Gauthier-Villars
VL - 47
IS - 4
SP - 929
EP - 968
AB - 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 &gt; 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 &lt; u⋆, then the largest component of the vacant set has a volume of order n, and if u &gt; 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.
LA - eng
KW - random walk; vacant set; regular graph; expanders; random interlacement; phase transition; simple random walk; trajectory; random interlacement model; fixed positive parameter; largest component; percolative properties; tree-like structure; threshold
UR - http://eudml.org/doc/243363
ER -

References

top
  1. [1] D. J. Aldous and M. Brown. Inequalities for rare events in time-reversible Markov chains. II. Stochastic Process. Appl. 44 (1993) 15–25. Zbl0812.60054MR1198660
  2. [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. [3] N. Alon, I. Benjamini and A. Stacey. Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 (2004) 1727–1745. Zbl1046.05071MR2073175
  4. [4] K. B. Athreya. Large deviation rates for branching processes. I. Single type case. Ann. Appl. Probab. 4 (1994) 779–790. Zbl0806.60068MR1284985
  5. [5] K. B. Athreya and P. E. Ney. Branching Processes. Die Grundlehren der Mathematischen Wissenschaften 196. Springer, New York, 1972. Zbl0259.60002MR373040
  6. [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. Zbl1141.60057MR2349899
  7. [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. Zbl1076.05071MR2155704
  8. [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. [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. Zbl1105.60029MR2240791
  10. [10] R. Durrett. Probability: Theory and Examples, 2nd edition. Duxbury Press, Belmont, CA, 1996. Zbl1202.60002MR1609153
  11. [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. Zbl0103.16301MR125031
  12. [12] J. Friedman. On the second eigenvalue and random walks in random d-regular graphs. Combinatorica 11 (1991) 331–362. Zbl0760.05078MR1137767
  13. [13] J. Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc. 195 (2008) viii+100. Zbl1177.05070MR2437174
  14. [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. Zbl1202.60012MR2667423
  15. [15] A. Lubotzky, R. Phillips and P. Sarnak. Ramanujan graphs. Combinatorica 8 (1988) 261–277. Zbl0661.05035MR963118
  16. [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. Zbl0712.05012MR1036755
  17. [17] A. Nachmias and Y. Peres. Critical percolation on random regular graphs. Random Structures Algorithms 36 (2010) 111–148. Available at arXiv:0707.2839. Zbl1209.05228MR2583058
  18. [18] B. Pittel. Edge percolation on a random regular graph of low degree. Ann. Probab. 36 (2008) 1359–1389. Zbl1160.05054MR2435852
  19. [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. Zbl0885.60061MR1490046
  20. [20] V. Sidoravicius and A.-S. Sznitman. Percolation for the vacant set of random interlacements. Comm. Pure Appl. Math. 62 (2009) 831–858. Zbl1168.60036MR2512613
  21. [21] A.-S. Sznitman. A lower bound on the critical parameter of interlacement percolation in high dimension. Probab. Theory Related Fields. To appear (2011). Zbl1230.60103MR2778797
  22. [22] A.-S. Sznitman. On the domination of random walk on a discrete cylinder by random interlacements. Electron. J. Probab. 14 (2009) 1670–1704. Zbl1196.60170MR2525107
  23. [23] A.-S. Sznitman. Random walks on discrete cylinders and random interlacements. Probab. Theory Related Fields 145 (2009) 143–174. Zbl1172.60316MR2520124
  24. [24] A.-S. Sznitman. Upper bound on the disconnection time of discrete cylinders and random interlacements. Ann. Probab. 37 (2009) 1715–1746. Zbl1179.60025MR2561432
  25. [25] A.-S. Sznitman. Vacant set of random interlacements and percolation. Ann. of Math. (2) 171 (2010) 2039–2087. Zbl1202.60160MR2680403
  26. [26] A. Teixeira. Interlacement percolation on transient weighted graphs. Electron. J. Probab. 14 (2009) 1604–1628. Zbl1192.60108MR2525105
  27. [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. Zbl1235.60143MR2838338
  28. [28] D. Windisch. Random walk on a discrete torus and random interlacements. Electron. Commun. Probab. 13 (2008) 140–150. Zbl1187.60089MR2386070

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.