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

Itai Benjamini¹ ; Harry Kesten² ; Yuval Peres³ ; Oded Schramm⁴

¹ Department of Mathematics, The Weizmann Institute of Science, 76100 Rehovot, Israel
² Department of Mathematics, Cornell University, Ithaca, NY 14853, United States
³ Department of Mathematics, University of California, Berkeley, Berkeley, CA 94702, United States
⁴ Microsoft Corporation, One Microsoft Way, Redmond, WA 98052, United States

Annals of mathematics, Tome 160 (2004) no. 2, pp. 465-491.

Résumé

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.

Détail

DOI : 10.4007/annals.2004.160.465