The Problem of Predecessors on Spanning Trees

Acta Polytechnica

V. S. Poghosyan¹  V. B. Priezzhev¹ 

关键词: loop erased random walk;    spanning trees;    Kirchhoff theorem;    Abelian sandpile model;   

DOI  :  

来源: Czech Technical University in Prague, Faculty of M

【 摘 要 】

We consider the equiprobable distribution of spanning trees on the square lattice. All bonds of each tree can be oriented uniquely with respect to an arbitrary chosen site called the root. The problem of predecessors is to find the probability that a path along the oriented bonds passes sequentially fixed sitesiandj . The conformal field theory for the Potts model predicts the fractal dimension of the path to be 5/4. Using this result, we show that the probability in the predecessors problem for two sites separated by large distancerdecreases asP ( r )∼ r −3/4 . If sitesiandjare nearest neighbors on the square lattice, the probabilityP (1) = 5 / 16 can be found from the analytical theory developed for the sandpile model. The known equivalence between the loop erased random walk (LERW) and the directed path on the spanning tree states thatP (1) is the probability for the LERW started atito reach the neighboring sitej . By analogy with the self-avoiding walk,P (1) can be called the return probability. Extensive Monte-Carlo simulations confirm the theoretical predictions.

【 授权许可】

Unknown