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

Kenyon, Richard; Wilson, David

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

Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs
HTML articles powered by AMS MathViewer

by Richard W. Kenyon and David B. Wilson;

J. Amer. Math. Soc. 28 (2015), 985-1030

DOI: https://doi.org/10.1090/S0894-0347-2014-00819-5

Published electronically: October 21, 2014

PDF

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

Itai Benjamini, Russell Lyons, Yuval Peres, and Oded Schramm, Uniform spanning forests, Ann. Probab. 29 (2001), no. 1, 1–65. MR 1825141, DOI 10.1214/aop/1008956321
Per Bak, Chao Tang, and Kurt Wiesenfeld, Self-organized criticality, Phys. Rev. A (3) 38 (1988), no. 1, 364–374. MR 949160, DOI 10.1103/PhysRevA.38.364
Ulrike Bücking, Approximation of conformal mappings by circle patterns, Geom. Dedicata 137 (2008), 163–197. MR 2449151, DOI 10.1007/s10711-008-9292-7
Yves Colin de Verdière, Réseaux électriques planaires. I, Comment. Math. Helv. 69 (1994), no. 3, 351–374 (French). MR 1289333, DOI 10.1007/bf02564493
Yves Colin de Verdière, Isidoro Gitler, and Dirk Vertigan, Réseaux électriques planaires. II, Comment. Math. Helv. 71 (1996), no. 1, 144–167 (French). MR 1371682, DOI 10.1007/BF02566413
E. B. Curtis, D. Ingerman, and J. A. Morrow, Circular planar graphs and resistor networks, Linear Algebra Appl. 283 (1998), no. 1-3, 115–150. MR 1657214, DOI 10.1016/S0024-3795(98)10087-3
Gabriel D. Carroll and David Speyer, The cube recurrence, Electron. J. Combin. 11 (2004), no. 1, Research Paper 73, 31. MR 2097339, DOI 10.37236/1826
A. Dvoretzky and Th. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947), 305–313. MR 21531, DOI 10.1215/S0012-7094-47-01423-3
Freeman J. Dyson, Correlations between eigenvalues of a random matrix, Comm. Math. Phys. 19 (1970), 235–250. MR 278668, DOI 10.1007/BF01646824
Nachum Dershowitz and Shmuel Zaks, The cycle lemma and some applications, European J. Combin. 11 (1990), no. 1, 35–40. MR 1034142, DOI 10.1016/S0195-6698(13)80053-4
Vladimir Fock and Alexander Goncharov, Moduli spaces of local systems and higher Teichmüller theory, Publ. Math. Inst. Hautes Études Sci. 103 (2006), 1–211. MR 2233852, DOI 10.1007/s10240-006-0039-4
Ilse Fischer and Philippe Nadeau, Fully packed loops in a triangle: matchings, paths and puzzles, arXiv:1209.1262.
Sergey Fomin, Loop-erased walks and total positivity, Trans. Amer. Math. Soc. 353 (2001), no. 9, 3563–3583. MR 1837248, DOI 10.1090/S0002-9947-01-02824-0
Robin Forman, Determinants of Laplacians on graphs, Topology 32 (1993), no. 1, 35–46. MR 1204404, DOI 10.1016/0040-9383(93)90035-T
Yasunari Fukai and Kôhei Uchiyama, Potential kernel for two-dimensional random walk, Ann. Probab. 24 (1996), no. 4, 1979–1992. MR 1415236, DOI 10.1214/aop/1041903213
Monwhea Jeng, Geoffroy Piroux, and Philippe Ruelle, Height variables in the abelian sandpile model: scaling fields and correlations, J. Stat. Mech. (2006), P10015.
Richard Kenyon, The asymptotic determinant of the discrete Laplacian, Acta Math. 185 (2000), no. 2, 239–286. MR 1819995, DOI 10.1007/BF02392811
Richard Kenyon, Long-range properties of spanning trees, J. Math. Phys. 41 (2000), no. 3, 1338–1363. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. MR 1757962, DOI 10.1063/1.533190
R. Kenyon, The Laplacian and Dirac operators on critical planar graphs, Invent. Math. 150 (2002), no. 2, 409–439. MR 1933589, DOI 10.1007/s00222-002-0249-4
Richard Kenyon, Spanning forests and the vector bundle Laplacian, Ann. Probab. 39 (2011), no. 5, 1983–2017. MR 2884879, DOI 10.1214/10-AOP596
Jang Soo Kim, Proofs of two conjectures of Kenyon and Wilson on Dyck tilings, J. Combin. Theory Ser. A 119 (2012), no. 8, 1692–1710. MR 2946383, DOI 10.1016/j.jcta.2012.05.008
G. Kirchhoff, Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird, Ann. Phys. und Chem. 72 (1847), no. 12, 497–508.
Jang Soo Kim, Karola Mészáros, Greta Panova, and David B. Wilson, Dyck tilings, increasing trees, descents, and inversions, J. Combin. Theory Ser. A 122 (2014), 9–27. MR 3127675, DOI 10.1016/j.jcta.2013.09.008
Gady Kozma and Ehud Schreiber, An asymptotic expansion for the discrete harmonic potential, Electron. J. Probab. 9 (2004), no. 1, 1–17. MR 2041826, DOI 10.1214/EJP.v9-170
Richard W. Kenyon and David B. Wilson, Boundary partitions in trees and dimers, Trans. Amer. Math. Soc. 363 (2011), no. 3, 1325–1364. MR 2737268, DOI 10.1090/S0002-9947-2010-04964-5
Richard W. Kenyon and David B. Wilson, Double-dimer pairings and skew Young diagrams, Electron. J. Combin. 18 (2011), no. 1, Paper 130, 22. MR 2811099, DOI 10.37236/617
Gregory F. Lawler, Intersections of random walks, Probability and its Applications, Birkhäuser Boston, Inc., Boston, MA, 1991. MR 1117680
Gregory F. Lawler, Loop-erased random walk, Perplexing problems in probability, Progr. Probab., vol. 44, Birkhäuser Boston, Boston, MA, 1999, pp. 197–217. MR 1703133
Gregory F. Lawler and Vlada Limic, Random walk: a modern introduction, Cambridge Studies in Advanced Mathematics, vol. 123, Cambridge University Press, Cambridge, 2010. MR 2677157, DOI 10.1017/CBO9780511750854
Thomas Lam and Pavlo Pylyavskyy, Inverse problem in cylindrical electrical networks, SIAM J. Appl. Math. 72 (2012), no. 3, 767–788. MR 2968749, DOI 10.1137/110846476
Lionel Levine and Yuval Peres, The looping constant of $\Bbb Z^d$, Random Structures Algorithms 45 (2014), no. 1, 1–13. MR 3231081, DOI 10.1002/rsa.20478
Gregory F. Lawler, Oded Schramm, and Wendelin Werner, Conformal invariance of planar loop-erased random walks and uniform spanning trees, Ann. Probab. 32 (2004), no. 1B, 939–995. MR 2044671, DOI 10.1214/aop/1079021469
Russell Lyons (with Yuval Peres), Probability on trees and networks, Cambridge University Press, 2014, in preparation. http://mypage.iu.edu/~rdlyons/prbtree/.
S. N. Majumdar and Deepak Dhar, Equivalence between the Abelian sandpile model and the $q\to 0$ limit of the Potts model, Physica A 185 (1992), 129–145.
Robin Pemantle, Choosing a spanning tree for the integer lattice uniformly, Ann. Probab. 19 (1991), no. 4, 1559–1574. MR 1127715
V. S. Poghosyan and V. B. Priezzhev, The problem of predecessors on spanning trees, Acta Polytechnica 51 (2011), no. 1, 59–62, arXiv:1010.5415.
Vahagn S. Poghosyan, Vyatcheslav B. Priezzhev, and Philippe Ruelle, Return probability for the loop-erased random walk and mean height in sandpile: a proof, J. Stat. Mech. Theory Exp. (2011), P10004.
V. B. Priezzhev, Structure of two-dimensional sandpile. I. Height probabilities, J. Stat. Phys. 74 (1994), 955–979.
Frank Spitzer, Principles of random walk, 2nd ed., Graduate Texts in Mathematics, Vol. 34, Springer-Verlag, New York-Heidelberg, 1976. MR 388547, DOI 10.1007/978-1-4684-6257-9
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
Alfred Stöhr, Über einige lineare partielle Differenzengleichungen mit konstanten Koeffizienten. III. Zweites Beispiel: Der Operator $\nabla \Phi (y_1,y_2)=\Phi (y_1+1, y_2)+\Phi (y_1-1, y_2)+\Phi (y_1, y_2+1)+\Phi (y_1, y_2-1)-4\Phi (y_1, y_2)$, Math. Nachr. 3 (1950), 330–357 (German). MR 40555, DOI 10.1002/mana.19490030603
Keiichi Shigechi and Paul Zinn-Justin, Path representation of maximal parabolic Kazhdan-Lusztig polynomials, J. Pure Appl. Algebra 216 (2012), no. 11, 2533–2548. MR 2927185, DOI 10.1016/j.jpaa.2012.03.027
David Bruce Wilson, Generating random spanning trees more quickly than the cover time, Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996) ACM, New York, 1996, pp. 296–303. MR 1427525, DOI 10.1145/237814.237880