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

Abstract

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

References in corpus (7)

• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Percolation on finite graphs and isoperimetric inequalities
• On the fragmentation of a torus by random walk
• Upper bound on the disconnection time of discrete cylinders and random interlacements
• Edge percolation on a random regular graph of low degree
• On the critical parameter of interlacement percolation in high dimension
• Interlacement percolation on transient weighted graphs

Cited by in corpus (17)

• Soft local times and decoupling of random interlacements
• Decoupling inequalities and interlacement percolation on G x Z
• On the fragmentation of a torus by random walk
• On scaling limits and Brownian interlacements
• A lower bound for disconnection by random interlacements
• Random interlacements and amenability
• Local picture and level-set percolation of the Gaussian free field on a large discrete torus
• A lower bound for disconnection by simple random walk
• Large deviations for occupation time profiles of random interlacements
• Percolation Perspective on Sites Not Visited by a Random Walk in Two Dimensions
• On the critical parameter of interlacement percolation in high dimension
• Universality of trap models in the ergodic time scale
• Critical window for the vacant set left by random walk on random regular graphs
• On the trace of random walks on random graphs
• Anatomy of a gaussian giant: supercritical level-sets of the free field on random regular graphs
• Aging of the Metropolis dynamics on the Random Energy Model
• Quasi-processes for branching Markov chains