Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs
Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs
复制标题
曲面上图的生成树以及平面图上循环擦除随机游走的强度
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
D. Wilson
中科院分区：
文献类型：
--
作者：
R. Kenyon;D. Wilson
我们展示了如何在嵌入在曲面上的图上计算均匀随机生成树的各种连接拓扑的概率。作为一个应用程序，我们展示了如何计算${mathbb Z}^2$中循环擦除随机游走的“强度”，即从（0,0）到无穷大经过给定顶点或边的概率。例如，它通过（1,0）的概率是5/16；这证实了1994年关于${mathbb Z}^2$上的固定沙堆密度的猜想。我们对三角形晶格、蜂窝晶格和${mathbb Z}次{mathbb R}$进行了类似的计算，它们的概率分别为5/18、13/36和$1/4-1/pi^2$。
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} imes {mathbb R}$, for which the probabilities are 5/18, 13/36, and $1/4-1/pi^2$ respectively.