Geometry of the uniform spanning forest: Transitions in dimensions 4, 8, 12,…

Abstract

The uniform spanning forest (USF) in $\mathbb{Z}^d$ is the weak limit of random, uniformly chosen, spanning trees in $[-n,n]^d$. Pemantle [11] proved that the USF consists a.s. of a single tree if and only if $d \le 4$. We prove that any two components of the USF in $\mathbb{Z}^d$ are adjacent a.s. if $5 \le d \le 8$, but not if $d \ge 9$. More generally, let $N(x,y)$ be the minimum number of edges outside the USF in a path joining $x$ and $y$ in $\mathbb{Z}^d$. Then \[ \max\bigl\{N(x,y): x,y\in\mathbb{Z}^d\bigr\} = \bigl\lfloor (d-1)/4 \bigr\rfloor \hbox{ a.s. } \] The notion of stochastic dimension for random relations in the lattice is introduced and used in the proof.

Authors

Itai Benjamini

Department of Mathematics
The Weizmann Institute of Science
76100 Rehovot
Israel

Harry Kesten

Department of Mathematics
Cornell University
Ithaca, NY 14853
United States

Yuval Peres

Department of Mathematics
University of California, Berkeley
Berkeley, CA 94702
United States

Oded Schramm

Microsoft Corporation
One Microsoft Way
Redmond, WA 98052
United States