Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs

Abstract

We show how to compute the probabilities of various connection topologies for uniformly random spanning trees on graphs embedded in surfaces. As an application, we show how to compute the "intensity" of the loop-erased random walk in ${\mathbb{Z}}^2$, that is, the probability that the walk from (0,0) to infinity passes through a given vertex or edge. For example, the probability that it passes through (1,0) is 5/16; this confirms a conjecture from 1994 about the stationary sandpile density on ${\mathbb{Z}}^2$. We do the analogous computation for the triangular lattice, honeycomb lattice and $\mathbb{Z}\times \mathbb{R}$, for which the probabilities are 5/18, 13/36, and $1/4-1/{\pi }^2$ respectively.

45 pages, many figures. v2 has an expanded introduction, a revised section on the LERW intensity, and an expanded appendix on the annular matrix

References in corpus (4)

• Approximation of conformal mappings by circle patterns
• Return probability for the loop-erased random walk and mean height in sandpile : a proof
• Dyck tilings, increasing trees, descents, and inversions
• Fully Packed Loops in a triangle: matchings, paths and puzzles

Cited by in corpus (20)

• Tree formulas, mean first passage times and Kemeny's constant of a Markov chain
• Discrete stress-energy tensor in the loop O(n) model
• Dyck tilings, increasing trees, descents, and inversions
• Boundary correlations in planar LERW and UST
• Sandpile models in the large
• Random two-component spanning forests
• Schramm's formula for multiple loop-erased random walks
• Sandpile probabilities on triangular and hexagonal lattices
• Pfaffian formulas for spanning tree probabilities
• Sandpiles and unicycles on random planar maps
• Bijections on Dyck tilings: DTS/DTR bijections, Dyck tableaux and tree-like tableaux
• Theory and Experiments for Disordered Elastic Manifolds, Depinning, Avalanches, and Sandpiles
• Scaling limit of the loop-erased random walk Green's function
• The looping constant of Z^d
• Multipoint correlators in the Abelian sandpile model
• Symmetric Dyck tilings, ballot tableaux and tree-like tableaux of shifted shapes
• Dyck tilings of type $D$
• Asymptotic height distribution in high-dimensional sandpiles
• Topology of a Uniform Spanning Tree on a Cylinder
• Laminations of a graph on a pair of pants