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

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?)


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

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

DOI: https://doi.org/10.1090/S0894-0347-2014-00819-5
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.