Giant vacant component left by a random walk in a random d-regular graph
Jiří Černý, Augusto Teixeira, David Windisch (2011)
Annales de l'I.H.P. Probabilités et statistiques
Similarity:
We study the trajectory of a simple random walk on a -regular graph with ≥ 3 and locally tree-like structure as the number of vertices grows. Examples of such graphs include random -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 , where > 0 is a fixed positive parameter. We show that this so-called set exhibits a phase transition in in the following sense: there exists...