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

Kenyon, Richard¹ ; Wilson, David²

¹ Department of Mathematics, Brown University, Providence, Rhode Island 02912
² Microsoft Research, Redmond, Washington 98052

Journal of the American Mathematical Society, Tome 28 (2015) no. 4, pp. 985-1030

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-2014-00819-5

Bibliographie

[1] Benjamini, Itai, Lyons, Russell, Peres, Yuval, Schramm, Oded Uniform spanning forests Ann. Probab. 2001 1 65

[2] Bak, Per, Tang, Chao, Wiesenfeld, Kurt Self-organized criticality Phys. Rev. A (3) 1988 364 374

[3] Bã¼Cking, Ulrike Approximation of conformal mappings by circle patterns Geom. Dedicata 2008 163 197

[4] Colin De Verdiã¨Re, Yves Réseaux électriques planaires. I Comment. Math. Helv. 1994 351 374

[5] Colin De Verdiã¨Re, Yves, Gitler, Isidoro, Vertigan, Dirk Réseaux électriques planaires. II Comment. Math. Helv. 1996 144 167

[6] Curtis, E. B., Ingerman, D., Morrow, J. A. Circular planar graphs and resistor networks Linear Algebra Appl. 1998 115 150

[7] Carroll, Gabriel D., Speyer, David The cube recurrence Electron. J. Combin. 2004

[8] Dvoretzky, A., Motzkin, Th. A problem of arrangements Duke Math. J. 1947 305 313

[9] Dyson, Freeman J. Correlations between eigenvalues of a random matrix Comm. Math. Phys. 1970 235 250

[10] Dershowitz, Nachum, Zaks, Shmuel The cycle lemma and some applications European J. Combin. 1990 35 40

[11] Fock, Vladimir, Goncharov, Alexander Moduli spaces of local systems and higher Teichmüller theory Publ. Math. Inst. Hautes Études Sci. 2006 1 211

[12] Fomin, Sergey Loop-erased walks and total positivity Trans. Amer. Math. Soc. 2001 3563 3583

[13] Forman, Robin Determinants of Laplacians on graphs Topology 1993 35 46

[14] Fukai, Yasunari, Uchiyama, Kã´Hei Potential kernel for two-dimensional random walk Ann. Probab. 1996 1979 1992

[15] Kenyon, Richard The asymptotic determinant of the discrete Laplacian Acta Math. 2000 239 286

[16] Kenyon, Richard Long-range properties of spanning trees J. Math. Phys. 2000 1338 1363

[17] Kenyon, R. The Laplacian and Dirac operators on critical planar graphs Invent. Math. 2002 409 439

[18] Kenyon, Richard Spanning forests and the vector bundle Laplacian Ann. Probab. 2011 1983 2017

[19] Kim, Jang Soo Proofs of two conjectures of Kenyon and Wilson on Dyck tilings J. Combin. Theory Ser. A 2012 1692 1710

[20] Kim, Jang Soo, Mã©Szã¡Ros, Karola, Panova, Greta, Wilson, David B. Dyck tilings, increasing trees, descents, and inversions J. Combin. Theory Ser. A 2014 9 27

[21] Kozma, Gady, Schreiber, Ehud An asymptotic expansion for the discrete harmonic potential Electron. J. Probab. 2004

[22] Kenyon, Richard W., Wilson, David B. Boundary partitions in trees and dimers Trans. Amer. Math. Soc. 2011 1325 1364

[23] Kenyon, Richard W., Wilson, David B. Double-dimer pairings and skew Young diagrams Electron. J. Combin. 2011

[24] Lawler, Gregory F. Intersections of random walks 1991 219

[25] Lawler, Gregory F. Loop-erased random walk 1999 197 217

[26] Lawler, Gregory F., Limic, Vlada Random walk: a modern introduction 2010

[27] Lam, Thomas, Pylyavskyy, Pavlo Inverse problem in cylindrical electrical networks SIAM J. Appl. Math. 2012 767 788

[28] Levine, Lionel, Peres, Yuval The looping constant of ℤ^{𝕕} Random Structures Algorithms 2014 1 13

[29] Lawler, Gregory F., Schramm, Oded, Werner, Wendelin Conformal invariance of planar loop-erased random walks and uniform spanning trees Ann. Probab. 2004 939 995

[30] Pemantle, Robin Choosing a spanning tree for the integer lattice uniformly Ann. Probab. 1991 1559 1574

[31] Spitzer, Frank Principles of random walk 1976

[32] Stanley, Richard P. Enumerative combinatorics. Vol. 2 1999

[33] Stã¶Hr, Alfred Über einige lineare partielle Differenzengleichungen mit konstanten Koeffizienten. III. Zweites Beispiel: Der Operator ∇Φ(𝑦₁,𝑦₂) Math. Nachr. 1950 330 357

[34] Shigechi, Keiichi, Zinn-Justin, Paul Path representation of maximal parabolic Kazhdan-Lusztig polynomials J. Pure Appl. Algebra 2012 2533 2548

[35] Wilson, David Bruce Generating random spanning trees more quickly than the cover time 1996 296 303