On the fragmentation of a torus by random walk

Abstract

Abstract We consider a simple random walk on a discrete torus \input amssym $({\Bbb Z}/N{\Bbb Z})^d$ with dimension d ≥ 3 and large side length N . For a fixed constant u ≥ 0, we study the percolative properties of the vacant set, consisting of the set of vertices not visited by the random walk in its first [ uN d ] steps. We prove the existence of two distinct phases of the vacant set in the following sense: If u > 0 is chosen large enough, all components of the vacant set contain no more than (log N ) λ( u ) vertices with high probability as N tends to infinity. On the other hand, for small u > 0, there exists a macroscopic component of the vacant set occupying a nondegenerate fraction of the total volume N d . In dimensions d ≥ 5, we additionally prove that this macroscopic component is unique by showing that all other components have volumes of order at most (log N ) λ( u ) . Our results thus solve open problems posed by Benjamini and Sznitman, who studied the small u regime in high dimension. The proofs are based on a coupling of the random walk with random interlacements on \input amssym ${\Bbb Z}^d$ . Among other techniques, the construction of this coupling employs a refined use of discrete potential theory. By itself, this coupling strengthens a result by Windisch. © 2011 Wiley Periodicals, Inc.