Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

   
 
 

 

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


Authors: Richard W. Kenyon and David B. Wilson
Journal: J. Amer. Math. Soc. 28 (2015), 985-1030
MSC (2010): Primary 60C05, 82B20, 05C05, 05C50
DOI: https://doi.org/10.1090/S0894-0347-2014-00819-5
Published electronically: October 21, 2014
MathSciNet review: 3369907
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 $\infty$ 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.


References [Enhancements On Off] (What's this?)

References

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 60C05, 82B20, 05C05, 05C50

Retrieve articles in all journals with MSC (2010): 60C05, 82B20, 05C05, 05C50


Additional Information

Richard W. Kenyon
Affiliation: Department of Mathematics, Brown University, Providence, Rhode Island 02912
MR Author ID: 307971

David B. Wilson
Affiliation: Microsoft Research, Redmond, Washington 98052

Keywords: Uniform spanning tree, loop-erased random walk, abelian sandpile model, vector-bundle Laplacian
Received by editor(s): July 19, 2011
Received by editor(s) in revised form: August 12, 2013, February 12, 2014, May 6, 2014, May 22, 2014, and June 5, 2014
Published electronically: October 21, 2014
Additional Notes: The research of the first author was supported by the NSF
Article copyright: © Copyright 2014 by the authors. This paper or any part thereof may be reproduced for non-commercial purposes.