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


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.


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