The union of independent USFs on $\mathbb{Z}^d$ is transient

Eleanor Archer, Asaf Nachmias, Matan Shalev, Pengfei TangarXiv 2023 · DOI · arXiv

TL;DR

In dimensions $d \geq 3$, a single Uniform Spanning Forest (USF) is "recurrent"—a random walk on it will eventually return to its starting point with probability 1. This paper proves that the union of just two independent USFs (or even a single USF with a tiny bit of extra percolation) is "transient," meaning there is a non-zero chance the random walk wanders off to infinity forever.

What Problem Does This Paper Address?

The study of Uniform Spanning Forests (USFs) is a cornerstone of modern probability theory, sitting at the intersection of graph theory, electrical networks, and statistical physics. On a finite graph, a Uniform Spanning Tree (UST) is simply a tree chosen uniformly at random from all possible spanning trees. On infinite lattices like $\mathbb{Z}^d$, the USF is the limit of these trees as the graph grows.

A famous result by Ben Morris (2003) established that every component of a USF is recurrent. This makes the USF a "critical" model—it's just barely connected enough to be a forest, but sparse enough that you can't escape to infinity.

The authors of this paper ask: Is this property stable? If we take two independent USFs and look at their union, does the graph become "supercritical" and transient? This question explores how much "extra" connectivity is needed to fundamentally change the behavior of a random walk on these random structures.

Methods

The proof relies on a sophisticated blend of combinatorial probability and geometric analysis. The authors don't just compare two USFs; they prove a more general result (Theorem 1.1) involving the union of an "everywhere percolating" subgraph and an $\epsilon$-Bernoulli percolation on a USF.

Key techniques include:

  • Box Percolation: The authors introduce a novel "box percolation" model. This is a specific way to partition the edges of $\mathbb{Z}^d$ into finite subgraphs that helps manage the dependencies inherent in USFs.
  • Stochastic Domination: They use Kirchhoff’s formula and effective resistance bounds to show that a USF "stochastically dominates" their box percolation model. This allows them to trade the complex, long-range dependencies of the USF for a more manageable, local model.
  • Spatial Sprinkling: Borrowing and adapting a technique from Benjamini and Tassion (2017), the authors use "sprinkling." They look at the graph in concentric annuli (rings) and show that adding a few edges in each ring exponentially reduces the number of connected components, eventually merging them into a single transient cluster.
  • Renormalization: By proving that local connectivity is high with very high probability, they use renormalization to show that the global structure must be transient for $d \geq 3$.

Datasets

Not discussed in the paper. As a theoretical mathematics paper, it relies on rigorous proofs rather than empirical data or benchmarks.

Key Insights and Ideas

  • The "1 + $\epsilon$" Transition: The most striking insight is that you don't need two full USFs to achieve transience. Even a single USF plus a tiny fraction ($\epsilon$) of its own edges (sampled independently) is enough to break the recurrence.
  • Geometry Matters: The proof heavily exploits the geometry of $\mathbb{Z}^d$. Because components of an "everywhere percolating" set must reach infinity, their boundaries are large. This "largeness" ensures there are plenty of opportunities for the "sprinkled" edges to bridge gaps between components.
  • Effective Resistance as a Bridge: The paper elegantly uses the relationship between random walks and electrical networks. By bounding the effective resistance, they provide the necessary "push" to prove that the random walk can escape to infinity.

Key Results

  • Theorem 1.1: For $d \geq 3$, the union of an everywhere percolating subgraph and an independent $\epsilon$-WUSF is almost surely connected and transient.
  • Corollary 1.2: The union of two independent samples of the WUSF on $\mathbb{Z}^d$ ($d \geq 3$) is almost surely connected and transient.
  • Connectivity: Beyond just being transient, the resulting union is almost surely a single connected component, rather than a collection of disjoint infinite clusters.

Limitations and Future Work

The authors highlight several intriguing open problems:

  • General Graphs: While they proved this for the lattice $\mathbb{Z}^d$, they conjecture (Conjecture 1.3) that this behavior holds on any transitive transient graph.
  • Spectral Dimension: In supercritical Bernoulli percolation, the "spectral dimension" (which governs the return probability of a random walk) is known to be $d$. The authors ask if the same is true for these USF unions (Question 1.4).
  • Invariance Principle: Does a simple random walk on these unions converge to Brownian motion? This is a standard "gold standard" for understanding random media that remains unproven for this specific model.

Summary updated

Abstract

We show that the union of two or more independent uniform spanning forests (USF) on $\mathbb{Z}^d$ with $d\geq 3$ almost surely forms a connected transient graph. In fact, this also holds when taking the union of a deterministic everywhere percolating set and an independent $ε$-Bernoulli percolation on a single USF sample.
BibTeX
@misc{archer2023union,
  author = {Eleanor Archer and Asaf Nachmias and Matan Shalev and Pengfei Tang},
  title = {{The union of independent USFs on $\textbackslash\{\}mathbb\{Z\}^d$ is transient}},
  year = {2023},
  eprint = {2311.09183},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.09183},
}
Figure