wykresx.eps Acta Polytechnica Vol. 51 No. 1/2011 The Problem of Predecessors on Spanning Trees V. S. Poghosyan, V. B. Priezzhev Abstract 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 sites i and j. 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 distance r decreases as P(r) ∼ r−3/4. If sites i and j are nearest neighbors on the square lattice, the probability P(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 that P(1) is the probability for the LERW started at i to reach the neighboring site j. By analogy with the self-avoiding walk, P(1) can be called the return probability. Extensive Monte-Carlo simulations confirm the theoretical predictions. Keywords: loop erased random walk, spanning trees, Kirchhoff theorem, Abelian sandpile model. 1 Introduction and main results Ingraphtheory, the spanning treeof connectedgraph G is a connected subgraphof G containingall vertices of G and having no cycles. Numerous applications of spanning trees began with Kirchhoff’s seminal problem solved in 1847, and then spread out many branches of mathematics and theoretical physics. In statistical mechanics, spanning trees are related to the Potts model [1], the dimer model [2], the sand- pile model [3] and many others. A relation between lattice models of statistical mechanics and spanning trees via the Tutte polynomial has been established by Fortuin and Kasteleyn [4]. TheKirchhoff theorem claims that the number of spanning trees of connected graph G is a cofactor of the Laplacian matrix Δ of graph G. If one deletes any row and any column from Δ, one obtains a ma- trix Δ∗ which gives the number of spanning trees as detΔ∗. The determinantal structure allows easy cal- culation of local characteristics of the spanning trees, for instance, the average number of vertices with a given number of adjacent bonds. A characterization of non-local objects in the spanning tree is not so simple. One such object is the chemical path defined as a path along two or more bonds of the tree. The fractal dimension of a long chemical path on the two- dimensional lattice has been calculated by means of a mapping of the spanning tree configurations onto the Coulomb gas model. A closely related object is the loop erased random walk (LERW) on the two-dimensional lattice [11], which was proven to be equivalent to the directed chemical path of the spanning tree of the same lat- tice [7, 12]. In this paper,we consider a problemaris- ing in the theory of LERW and equally distributed spanning trees: given two lattice sites i and j, what is the probability that the LERWor the directed chem- ical path passes i and j? If site i is passed first, we say that i is the predecessor of j and we refer to this problem as the predecessor problem. Surprisingly, the problemhasno exact solution in the general case. Only two limiting casesareavailable: (a) If sites i and j are separated by large distance r, the asymptotics of P(r) can be found fromknown results on the frac- tal dimension of the chemical path; (b) If points i and j are nearest neighbors of the square lattice, the seeking probability can be found from the theory of sandpiles [9] (see also [16]). The asymptotic behavior of P(r) for large dis- tance r follows directly from the definition of the fractal dimension. Indeed, consider a large square lattice L and the set of uniformly distributed span- ning trees on L. We assume that the root is situated at the boundary of L. Consider site i in the bulk of the lattice and somecircle contour C of radius R with the center in i. Let Π be a directed chemical path from i to the root along the oriented bonds of a tree. All points of the subset ofΠ inside C are descendants of i. In accordance with the definition of the fractal dimension of the directed path on the spanning tree, the number of descendants inside C is proportional to R5/4 (see Majumdar [7]). The probability that point i is the predecessor of point j lying at distance r from i is the density of descendants ρ(r). Thus, we have 59 Acta Polytechnica Vol. 51 No. 1/2011 ∫ R 1 ρ(r)r dr ∼ R5/4 (1.1) from where we conclude that ρ(R) ∼ R−3/4. As was mentioned above, the problem of pre- decessors for an arbitrary disposition of two lattice points is not solved. In Section 2 we concentrate on a particular problemof probability P(1) when points i and j are nearest neighbors of the square lattice. An essential element of the theory of sandpiles is the probability distribution of sites having 0, 1, 2 and 3 predecessors among the nearest neighbors. The cor- responding probabilities are denoted by X0, X1, X2 and X3. Having explicit expressions for these values, we obtain P(1) as their combination and get an un- expectedly simple result P(1) = 5/16. In Section 3, we relate this result to the return probability of the LERW.Section 4 contains the results ofMonte-Carlo verifications. 2 The problem of predecessors for nearest neighbors The spanning tree enumeration method, namely the Kirchhoff theorem is proved to be a powerful math- ematical instrument for the investigation of various combinatorial problems in theoretical physics. In the last decade, it has been developed and adapted for calculating the height probabilities of the Abelian sandpilemodel [5, 9, 16]. TheAbelian sandpilemodel is a stochastic dynamical system,whichdescribes the phenomenon of self-organized criticality. During the evolution the system falls into a subset of all possi- ble states, called the subset of recurrent states. The problem is to calculate analytically various observ- able values in the recurrent state, such as height probabilities Pi, i =1,2,3,4atafixedsite andheight correlations between distinct fixed sites [18]. It was shown that the calculation of height prob- abilities in the Abelian sandpile can be reduced to the calculation of X0, X1, X2 and X3 in the span- ning tree model. The exact relation between these quantities is given by P1 = X0 4 ; P2 = P1 + X1 3 ; P3 = P2 + X2 2 ; P4 = P3 + X3. (2.2) Majumdar and Dhar [5] found in 1991 the prob- ability of height 1, constructing the corresponding defect lattice for the situation when a site i0 has no predecessors and calculating the determinant of the defect matrix Δ∗. A technique for computing the numbers X1, X2, X3 was devised in [9]. The results are (see also [16] for details) X0 = 8(π −2) π3 ; X1 = 3 4 + 48 π3 − 15 π2 − 3 2π ; X2 = 1 4 − 48 π3 + 6 π2 + 3 π ; (2.3) X3 = 16 π3 + 1 π2 − 3 2π , which give P1 = 2(π −2) π3 ; P2 = 1 4 + 12 π3 − 3 π2 − 1 2π ; P3 = 3 8 − 12 π3 + 1 π ; (2.4) P4 = 3 8 + 4 π3 + 1 π2 − 1 2π . Fig. 1: All possible situations with a fixed vertex i0 (the central vertex in the diagrams) to have various nearest neighbouringpredecessors on the square lattice. Byblack color we denote vertices, which are predecessors of i0. White means that the corresponding vertex is not a pre- decessor of i0. On the k+1st row(k =0,1,2,3) situations with k predecessors are presented. The configurations for which the right neighboring vertex is a predecessor of i0 are circled by a dashed line Now consider the problem of predecessors for nearest neighboring sites. First we fix a site i0 in the bulk of the square lattice. Denote its right near- est neighboring site by j0. Next consider four various cases, when i0 has exactly k nearest neighboring pre- decessors (k = 0,1,2,3) (see Fig. 1). For k = 0 the site j0 trivially is not a predecessor of i0. For k =1, we have 1 of 4 equivalent situations when j0 is the predecessor of i0. For k = 3, we have 3 of 4 equiva- lent situationswhen j0 is thepredecessor. Thecrucial case is k = 2. Here we have 6 situations, but not all of them are equivalent. On the other hand, we can select two groups of 4 and 2 elements (the first four and the last two in the third line of Fig. 1) so that 60 Acta Polytechnica Vol. 51 No. 1/2011 the elements in each group are equivalent. We are looking for situations where j0 is a predecessor of i0. There are 2 encircled elements from the first group and one from the second group, which correspond to the desired situations. Thus, if we take the lin- ear combination of X1, X2 and X3 with coefficients 1/4, 1/2 and 3/4 correspondingly, we get the desired probability P(1) that j0 is the predecessor of i0: P(1)= 1 4 X1 + 1 2 X2 + 3 4 X3 = 5 16 . (2.5) 3 Return probability for the loop erased random walk Consider a finite square lattice L with vertex set V and edge set E. Given P = [u0, u1, u2, . . . , un] a path in L, its loop-erasure LE(P) = [γ0, γ1, γ2, . . . , γm] is defined by chronologically removing loops from P. Formally, this definition is as follows. We first set γ0 = u0. Assuming γ0, . . . , γk have been defined, we let sk =1+max{j : uj = γk}. If sk = n+1, we stop and LE(P)= [γ0, γ1, γ2, . . . , γm] with m = k. Other- wise, we let γk+1 = usk. Note that the order inwhich we remove loops doesmatter, and it follows from the definition that we remove loops as they are created, following the path. A walk obtained after applying the loop-erasure to a simple random walk path is called a Loop-Erased Random Walk (LERW). Since the infinite simple random walk on finite connected undirected graphs is recurrent, the infinite LERW is not defined. On the other hand, we can fix a subset W ⊂ V of vertices and define LERW from a fixed vertex u0 to W . To do this, we take the path of a simple random walk started at u0 and stopped upon hitting W , after which we apply the loop-erasure. Wilson established an algorithm to generate uni- form spanning trees, which uses LERW [13]. It turns out to be extremely useful not only as a simulation tool, but also for theoretical analysis. It runs as fol- lows. Pickanarbitraryordering V = {v0, v1, . . . , vN } for the vertices in L. Let S0 = v0. Inductively, for i = 1,2, . . . , N define a graph Si to be the union of Si−1 and a (conditionally independent) LERW path from vi to Si−1. Note, if vi ∈ Si−1, then Si = Si−1. Then, regardless of the chosen order of the vertices, SN is a UST on L with root v0. If we take as an ini- tial condition S0 = W , with some W ⊂ V , then the generated structures will be spanning forests with a set of roots W . The spanning forest with a fixed set of roots can be considered as a spanning tree, if we add an auxiliary vertex and join it to all the roots. Nowconsider theWilson algorithmon L with the set of boundaryvertices ∂L and take S0 = ∂L. When the size of the lattice tends to infinity, the boundary effectswill vanish, sowe canneglect the details of the boundary. So we will not distinguish between span- ning forests and spanning trees. It follows from the Wilson algorithm for a fixed site i0, that if we start a LERWfrom i0 uponhitting theboundary ∂L, wewill generate a path � of a spanning tree from i0 to the boundary (see also [7, 8]). All vertices on the path � form the set of descendants of i0. So, if a fixed vertex j0 belongs to �, i0 is a predecessor of j0. Consequently, the probability P(j0−i0) that i0 is apredecessorof j0 in a randomlytaken (fromtheuni- form distribution) spanning tree on the large square lattice is equal to the probability that the LERW started from i0 passes j0. In the particular case |j0 − i0| =1, the probability P(1)= 5/16 calculated in the previous section is the return probability for the LERW. 4 Monte-Carlo simulations Consider the finite 2N +1 × 2N +1 square lattice LN. Denote its central vertex by i0 and assume that it is an origin of the coordinate system. We deliberately took an odd-odd lattice to provide the symmetry which guarantees the most efficient van- ishing of the boundary effects for large lattices. Af- ter generating a large number of LERWs starting from i0, we get an approximation of the function PN(j0−i0) ≡ PN(j0). Given fixed j0, we can extrap- olate PN(j0), tending N to infinity andgetasymptot- ical function P(j0). Assume that the Euclidean dis- tance between the origin i0 and j0 is r and the coor- dinates of j0 are (rcosϕ, r sinϕ). The Monte-Carlo simulations and Coulomb gas arguments show that the asymptotical behaviour of the function P(j0) for large r (r � 1) does not depend on ϕ. So, for r � 1 we have P(j0) � P(r). Fig. 2 shows the behaviour of P(r) for various j0 on the log-log scale, obtained from Monte-Carlo simulations. From this result we conclude that P(r) decreases as a power function: P(r) � C rα , (4.6) Fig. 2: The results of Monte-Carlo simulations for the probability P(r) 61 Acta Polytechnica Vol. 51 No. 1/2011 with α ≈ 0.751 and C ≈ 0.305. During the sim- ulations, we took sizes up to N = 100 and num- ber of simulations 108. The obtained results are in agreement with α = 3/4, which follows from the Coulomb gas arguments mentioned above. The ef- fective Monte-Carlo algorithm allows the evaluation of probabilities P(j0 − i0) for arbitrary finite j0, i0. At the same time, the analytical calculation of P(r) for r > 1 remains a difficult unsolved problem. Acknowledgement This work was supported by Russian RFBR grant No. 09-01-00271a, and by the Belgian Interuniver- sity Attraction Poles Program P6/02, through the NOSY (Nonlinear systems, stochastic processes and statistical mechanics) network. We would like to thank P. Ruelle for helpful discussions. The Monte- Carlo simulationswereperformedonArmenianClus- ter forHighPerformanceComputation (ArmCluster, http://www.cluster.am). References [1] Wu, F.Y.: Rev.Mod. Phys.54 (1982), 235–268. [2] Fisher, M. E., Stephenson, J.: Phys. Rev. 132 (1963), 1411–1431. [3] Bak, P., Tang, C., Wiesenfeld, K.: Phys. Rev. Lett. 59 (1987), 381; Dhar, D.: Phys. Rev. Lett. 64 (1990), 1613; Priezzhev, V. B., Ktitarev, D. V., Ivashkevich, E. V.: Phys. Rev. Lett. 76 (1996), 2093; Ivashkevich, E. V.: Phys. Rev. Lett. 76 (1996), 3368; Hu, C.-K., et al.: Phys. Rev. Lett. 85 (2000), 4048. [4] Fortuin, C. M., Kasteleyn, P. W.: Physica, 57, 4 (1972), 536–564. [5] Majumdar, S. N., Dhar, D.: J. Phys. A: Math. Gen. 24 (1991), L357. [6] Majumdar, S. N., Dhar, D.: Physica A 185 (1992), 129. [7] Majumdar, S. N.: Phys. Rev. Lett. 68 (1992), 2329–2331. [8] Lawler, G. F., Schramm, O., Werner, W.: An- nals of Prob. 32, 1B (2004), 939–995. [9] Priezzhev, V. B.: J. Stat. Phys. 74 (1994), 955. [10] Mahieu, S., Ruelle, P.: Phys. Rev. E 64 (2001), 066130; Ruelle, P.: Phys. Lett. B 539 (2002), 172; Jeng, M.: Phys. Rev. E 69 (2004), 051302; Jeng, M.: Phys. Rev. E 71 (2005), 036153; Jeng, M.: Phys. Rev. E 71 (2005), 016140;Moghimi-Araghi, S., Rajabpour,M. A., Rouhani, S.: Nucl. Phys. B 718 (2005), 362; Ruelle, P.: J. Stat. Mech. (2007), P09013. [11] Lawler, G. F.: Duke Math. J. 47, 3 (1980), 655–693. [12] Kenyon,R.: ActaMath.185, 2 (2000), 239–286. [13] Wilson, D.: Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing, ACM (1996), 296–303. [14] Piroux, G., Ruelle, P.: J. Stat Mech. (2004), P10005. [15] Piroux, G., Ruelle, P.: J. Phys. A: Math. Gen. 38 (2005), 1451. [16] Piroux,G.,Ruelle,P.: Phys. Lett.B 607 (2005), 188; Jeng, M., Piroux, G., Ruelle, P.: J. Stat. Mech. (2006), P10015. [17] Izmailian, N. Sh., Priezzhev, V. B., Ruelle, P., Hu, C.-K.: Phys. Rev. Lett. 95 (2005), 260602; Izmailian, N. Sh., Priezzhev, V. B., Ruelle, P.: Symmetry, Integr. Geom.: Methods Appl. 3 (2007), 001. [18] Poghosyan, V. S., Grigorev, S. Y., Priez- zhev, V. B., Ruelle, P.: Phys. Lett. B 659 (2008), 768; J. Stat. Mech. (2010), P07025. [19] Azimi-Tafreshi,N.,Dashti-Naserabadi,H.,Mog- himi-Araghi, S., Ruelle, P.: J. Stat. Mech. (2010), P02004. [20] Grigorev, S. Y., Poghosyan, V. S., Priez- zhev, V. B.: J. Stat. Mech. (2009), P09008. V. S. Poghosyan E-mail: vahagn.poghosyan@uclouvain.be Institute for Theoretical Physics The Catholic University of Louvain B-1348 Louvain-La-Neuve, Belgium V. B. Priezzhev E-mail: priezzvb@theor.jinr.ru Bogoliubov Laboratory of Theoretical Physics Joint Institute for Nuclear Research 141980Dubna, Russia 62