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

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

2010-12-22

arxiv.org/abs/1012.5117v1

Mathematics

Probability

Scientific paper

We study the trajectory of a simple random walk on a d-regular graph with d>2 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* such that, with high probability as n grows, if uu*, then it has a volume of order log(n). The critical value u* coincides with the critical intensity of a random interlacement process (introduced by Sznitman [arXiv:0704.2560]) on a d-regular tree. We also show that the random interlacement model describes the structure of the vacant set in local neighbourhoods.

Affiliated with

Also associated with

No associations

Rating

Giant vacant component left by a random walk in a random d-regular graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Giant vacant component left by a random walk in a random d-regular graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Giant vacant component left by a random walk in a random d-regular graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-295830