Boundary partitions in trees and dimers
HTML articles powered by AMS MathViewer
- by Richard W. Kenyon and David B. Wilson PDF
- Trans. Amer. Math. Soc. 363 (2011), 1325-1364 Request permission
Abstract:
Given a finite planar graph, a grove is a spanning forest in which every component tree contains one or more of a specified set of vertices (called nodes) on the outer face. For the uniform measure on groves, we compute the probabilities of the different possible node connections in a grove. These probabilities only depend on boundary measurements of the graph and not on the actual graph structure; i.e., the probabilities can be expressed as functions of the pairwise electrical resistances between the nodes, or equivalently, as functions of the Dirichlet-to-Neumann operator (or response matrix) on the nodes. These formulae can be likened to generalizations (for spanning forests) of Cardy’s percolation crossing probabilities and generalize Kirchhoff’s formula for the electrical resistance. Remarkably, when appropriately normalized, the connection probabilities are in fact integer-coefficient polynomials in the matrix entries, where the coefficients have a natural algebraic interpretation and can be computed combinatorially. A similar phenomenon holds in the so-called double-dimer model: connection probabilities of boundary nodes are polynomial functions of certain boundary measurements, and, as formal polynomials, they are specializations of the grove polynomials. Upon taking scaling limits, we show that the double-dimer connection probabilities coincide with those of the contour lines in the Gaussian free field with certain natural boundary conditions. These results have a direct application to connection probabilities for multiple-strand $\operatorname {SLE}_2$, $\operatorname {SLE}_8$, and $\operatorname {SLE}_4$.References
- Louis-Pierre Arguin and Yvan Saint-Aubin, Non-unitary observables in the 2d critical Ising model, Phys. Lett. B 541 (2002), no. 3-4, 384–389. MR 1928682, DOI 10.1016/S0370-2693(02)02228-1
- Michel Bauer, Denis Bernard, and Kalle Kytölä, Multiple Schramm-Loewner evolutions and statistical mechanics martingales, J. Stat. Phys. 120 (2005), no. 5-6, 1125–1163. MR 2187598, DOI 10.1007/s10955-005-7002-5
- Nathaniel D. Blair-Stahn and David B. Wilson, Electrical response matrix of a regular $2n$-gon, Proc. Amer. Math. Soc. 137 (2009), no. 6, 2015–2025. MR 2480283, DOI 10.1090/S0002-9939-09-09734-2
- John L. Cardy, Critical percolation in finite geometries, J. Phys. A 25 (1992), no. 4, L201–L206. MR 1151081
- John Cardy, ADE and SLE, J. Phys. A 40 (2007), no. 7, 1427–1438. MR 2303259, DOI 10.1088/1751-8113/40/7/001
- Yves Colin de Verdière, Spectres de graphes, Cours Spécialisés [Specialized Courses], vol. 4, Société Mathématique de France, Paris, 1998 (French, with English and French summaries). MR 1652692
- 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
- Mihai Ciucu, Enumeration of perfect matchings in graphs with reflective symmetry, J. Combin. Theory Ser. A 77 (1997), no. 1, 67–97. MR 1426739, DOI 10.1006/jcta.1996.2725
- Federico Camia and Charles M. Newman, Critical percolation exploration path and $\textrm {SLE}_6$: a proof of convergence, Probab. Theory Related Fields 139 (2007), no. 3-4, 473–519. MR 2322705, DOI 10.1007/s00440-006-0049-7
- Gabriel D. Carroll and David Speyer, The cube recurrence, Electron. J. Combin. 11 (2004), no. 1, Research Paper 73, 31. MR 2097339
- P. Di Francesco, O. Golinelli, and E. Guitter, Meanders and the Temperley-Lieb algebra, Comm. Math. Phys. 186 (1997), no. 1, 1–59. MR 1462755, DOI 10.1007/BF02885671
- Peter G. Doyle and J. Laurie Snell, Random walks and electric networks, Carus Mathematical Monographs, vol. 22, Mathematical Association of America, Washington, DC, 1984. MR 920811, DOI 10.5948/UPO9781614440222
- B. Duplantier and H. Saleur, Exact critical properties of two-dimensional dense self-avoiding walks, Nuclear Phys. B 290 (1987), no. 3, 291–326. MR 919521, DOI 10.1016/0550-3213(87)90190-8
- Julien Dubédat, Euler integrals for commuting SLEs, J. Stat. Phys. 123 (2006), no. 6, 1183–1218. MR 2253875, DOI 10.1007/s10955-006-9132-9
- Bertrand Duplantier, Critical exponents of Manhattan Hamiltonian walks in two dimensions, from Potts and $\textrm {O}(n)$ models, J. Statist. Phys. 49 (1987), no. 3-4, 411–431. MR 926190, DOI 10.1007/BF01009343
- Bertrand Duplantier, Statistical mechanics of polymer networks of any topology, J. Statist. Phys. 54 (1989), no. 3-4, 581–680. MR 988554, DOI 10.1007/BF01019770
- Bertrand Duplantier. Loop-erased self-avoiding walks in two dimensions: Exact critical exponents and winding numbers. Physica A, 191:516–522, 1992.
- Bertrand Duplantier. Conformal random geometry. In A. Bovier, F. Dunlop, A. van Enter, F. den Hollander, and J. Dalibard, editors, Mathematical Statistical Physics, Lecture Notes of the Les Houches Summer School Session LXXXIII, 2005, pages 101–217. Elsevier, 2006,
- 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
- V. F. R. Jones, Index for subfactors, Invent. Math. 72 (1983), no. 1, 1–25. MR 696688, DOI 10.1007/BF01389127
- P. W. Kasteleyn, Graph theory and crystal physics, Graph Theory and Theoretical Physics, Academic Press, London, 1967, pp. 43–110. MR 0253689
- Richard Kenyon, Local statistics of lattice dimers, Ann. Inst. H. Poincaré Probab. Statist. 33 (1997), no. 5, 591–618 (English, with English and French summaries). MR 1473567, DOI 10.1016/S0246-0203(97)80106-9
- Richard Kenyon, Conformal invariance of domino tiling, Ann. Probab. 28 (2000), no. 2, 759–795. MR 1782431, DOI 10.1214/aop/1019160260
- Gustav Kirchhoff, Beweis der Existenz des Potentials das an der Grenze des betrachteten Raumes gegebene Werthe hat für den Fall dass diese Grenze eine überall convexe Fläche ist, Acta Math. 14 (1890), no. 1, 179–183 (German). MR 1554794, DOI 10.1007/BF02413319
- Michael J. Kozdron and Gregory F. Lawler, The configurational measure on mutually avoiding SLE paths, Universality and renormalization, Fields Inst. Commun., vol. 50, Amer. Math. Soc., Providence, RI, 2007, pp. 199–224. MR 2310306, DOI 10.1088/1751-8113/45/49/494015
- Ki Hyoung Ko and Lawrence Smolinsky, A combinatorial matrix in $3$-manifold theory, Pacific J. Math. 149 (1991), no. 2, 319–336. MR 1105701, DOI 10.2140/pjm.1991.149.319
- Eric H. Kuo, Applications of graphical condensation for enumerating matchings and tilings, Theoret. Comput. Sci. 319 (2004), no. 1-3, 29–57. MR 2074946, DOI 10.1016/j.tcs.2004.02.022
- Richard W. Kenyon and David B. Wilson, Combinatorics of tripartite boundary connections for trees and dimers, Electron. J. Combin. 16 (2009), no. 1, Research Paper 112, 28. MR 2539354
- 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
- Kaoru Ohno and Kurt Binder, Scaling theory of star polymers and general polymer networks in bulk and semi-infinite good solvents, J. Physique 49 (1988), no. 8, 1329–1351 (English, with French summary). MR 966320, DOI 10.1051/jphys:019880049080132900
- Robin Pemantle, Uniform random spanning trees, Topics in contemporary probability and its applications, Probab. Stochastics Ser., CRC, Boca Raton, FL, 1995, pp. 1–54. MR 1410532
- T. Kyle Petersen and David Speyer, An arctic circle theorem for Groves, J. Combin. Theory Ser. A 111 (2005), no. 1, 137–164. MR 2144860, DOI 10.1016/j.jcta.2004.11.013
- H. Saleur. New exact exponents for two-dimensional self-avoiding walks. J. Phys. A, 19:L807–L810, 1986.
- Oded Schramm, Scaling limits of loop-erased random walks and uniform spanning trees, Israel J. Math. 118 (2000), 221–288. MR 1776084, DOI 10.1007/BF02803524
- Oded Schramm, Conformally invariant scaling limits: an overview and a collection of problems, International Congress of Mathematicians. Vol. I, Eur. Math. Soc., Zürich, 2007, pp. 513–543. MR 2334202, DOI 10.4171/022-1/20
- Stanislav Smirnov, Critical percolation in the plane: conformal invariance, Cardy’s formula, scaling limits, C. R. Acad. Sci. Paris Sér. I Math. 333 (2001), no. 3, 239–244 (English, with English and French summaries). MR 1851632, DOI 10.1016/S0764-4442(01)01991-7
- Stanislav Smirnov. Conformal invariance in random cluster models. I. Holomorphic fermions in the Ising model, 2007, arXiv:0708.0039.
- Frank Spitzer, Principles of random walk, 2nd ed., Graduate Texts in Mathematics, Vol. 34, Springer-Verlag, New York-Heidelberg, 1976. MR 0388547, DOI 10.1007/978-1-4684-6257-9
- Oded Schramm and Scott Sheffield, Contour lines of the two-dimensional discrete Gaussian free field, Acta Math. 202 (2009), no. 1, 21–137. MR 2486487, DOI 10.1007/s11511-009-0034-y
- Oded Schramm and Scott Sheffield, 2007. Personal communication.
- Richard P. Stanley, Enumerative combinatorics. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986. With a foreword by Gian-Carlo Rota. MR 847717, DOI 10.1007/978-1-4615-9763-6
- 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
- Oded Schramm and David B. Wilson. SLE, quadrangles, and curvilinear triangles, 2005.
- J. H. van Lint and R. M. Wilson, A course in combinatorics, Cambridge University Press, Cambridge, 1992. MR 1207813
Additional Information
- Richard W. Kenyon
- Affiliation: Department of Mathematics, Brown University, 151 Thayer Street, Providence, Rhode Island 02912
- David B. Wilson
- Affiliation: Microsoft Research, Redmond, Washington 98052
- Received by editor(s): March 26, 2008
- Received by editor(s) in revised form: November 25, 2008
- Published electronically: October 25, 2010
- © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 363 (2011), 1325-1364
- MSC (2010): Primary 60C05, 82B20, 05C05, 05C50
- DOI: https://doi.org/10.1090/S0002-9947-2010-04964-5
- MathSciNet review: 2737268