## A variational principle for domino tilings

HTML articles powered by AMS MathViewer

- by Henry Cohn, Richard Kenyon and James Propp PDF
- J. Amer. Math. Soc.
**14**(2001), 297-346 Request permission

## Abstract:

We formulate and prove a variational principle (in the sense of thermodynamics) for random domino tilings, or equivalently for the dimer model on a square grid. This principle states that a typical tiling of an arbitrary finite region can be described by a function that maximizes an entropy integral. We associate an entropy to every sort of local behavior domino tilings can exhibit, and prove that almost all tilings lie within $\varepsilon$ (for an appropriate metric) of the unique entropy-maximizing solution. This gives a solution to the dimer problem with fully general boundary conditions, thereby resolving an issue first raised by Kasteleyn. Our methods also apply to dimer models on other grids and their associated tiling models, such as tilings of the plane by three orientations of unit lozenges.## References

- H. W. J. Blöte and H. J. Hilhorst,
*Roughening transitions and the zero-temperature triangular Ising antiferromagnet*, J. Phys. A**15**(1982), no. 11, L631–L637. MR**679091** - Robert Burton and Robin Pemantle,
*Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances*, Ann. Probab.**21**(1993), no. 3, 1329–1371. MR**1235419** - Henry Cohn, Noam Elkies, and James Propp,
*Local statistics for random domino tilings of the Aztec diamond*, Duke Math. J.**85**(1996), no. 1, 117–166. MR**1412441**, DOI 10.1215/S0012-7094-96-08506-3 - Henry Cohn, Michael Larsen, and James Propp,
*The shape of a typical boxed plane partition*, New York J. Math.**4**(1998), 137–165. MR**1641839** - N. Destainville, R. Mosseri, and F. Bailly,
*Configurational entropy of codimension-one tilings and directed membranes*, J. Statist. Phys.**87**(1997), no. 3-4, 697–754. MR**1459040**, DOI 10.1007/BF02181243 - Hidegorô Nakano,
*Über Abelsche Ringe von Projektionsoperatoren*, Proc. Phys.-Math. Soc. Japan (3)**21**(1939), 357–375 (German). MR**94** - Herbert Federer,
*Geometric measure theory*, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York, Inc., New York, 1969. MR**0257325** - Jean-Claude Fournier,
*Pavage des figures planes sans trous par des dominos: fondement graphique de l’algorithme de Thurston et parallélisation*, C. R. Acad. Sci. Paris Sér. I Math.**320**(1995), no. 1, 107–112 (French, with English and French summaries). MR**1320841**, DOI 10.1016/0304-3975(95)00204-9 - David Gilbarg and Neil S. Trudinger,
*Elliptic partial differential equations of second order*, Grundlehren der Mathematischen Wissenschaften, Vol. 224, Springer-Verlag, Berlin-New York, 1977. MR**0473443**, DOI 10.1007/978-3-642-96379-7
[GP]GP D. Gupta and J. Propp, work in preparation.
[H]H M. Höffe, - M. T. Jaekel and J.-M. Maillard,
*Inversion relations and disorder solutions on Potts models*, J. Phys. A**17**(1984), no. 10, 2079–2094. MR**763798**, DOI 10.1088/0305-4470/17/10/020
[JPS]JPS W. Jockusch, J. Propp, and P. Shor, - P. W. Kasteleyn,
*Dimer statistics and phase transitions*, J. Mathematical Phys.**4**(1963), 287–293. MR**153427**, DOI 10.1063/1.1703953 - Claire Kenyon and Eric Rémila,
*Perfect matchings in the triangular lattice*, Discrete Math.**152**(1996), no. 1-3, 191–210. MR**1388642**, DOI 10.1016/0012-365X(94)00304-2 - 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
[Ke2]Kenyon2 R. Kenyon, - L. S. Levitov,
*Equivalence of the dimer resonating-valence-bond problem to the quantum roughening problem*, Phys. Rev. Lett.**64**(1990), no. 1, 92–94. MR**1031942**, DOI 10.1103/PhysRevLett.64.92 - J.-M. Maillard and R. Rammal,
*${\scr S}_4$-symmetry on the checkerboard Potts model*, J. Phys. A**18**(1985), no. 5, 833–846. MR**780515**, DOI 10.1088/0305-4470/18/5/016
[M]Mil J. Milnor, - James Propp,
*Boundary-dependent local behavior for $2$-D dimer models*, Proceedings of the Conference on Exactly Soluble Models in Statistical Mechanics: Historical Perspectives and Current Status (Boston, MA, 1996), 1997, pp. 183–187. MR**1435068**, DOI 10.1142/S0217979297000241 - James Gary Propp and David Bruce Wilson,
*Exact sampling with coupled Markov chains and applications to statistical mechanics*, Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), 1996, pp. 223–252. MR**1611693**, DOI 10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.3.CO;2-R - Walter Rudin,
*Real and complex analysis*, 3rd ed., McGraw-Hill Book Co., New York, 1987. MR**924157** - N. C. Saldanha, C. Tomei, M. A. Casarin Jr., and D. Romualdo,
*Spaces of domino tilings*, Discrete Comput. Geom.**14**(1995), no. 2, 207–233. MR**1331927**, DOI 10.1007/BF02570703 - H. N. V. Temperley and Michael E. Fisher,
*Dimer problem in statistical mechanics—an exact result*, Philos. Mag. (8)**6**(1961), 1061–1063. MR**136398**, DOI 10.1080/14786436108243366 - William P. Thurston,
*Conway’s tiling groups*, Amer. Math. Monthly**97**(1990), no. 8, 757–773. MR**1072815**, DOI 10.2307/2324578

*Zufallsparkettierungen und Dimermodelle*, Thesis, Institut für Theoretische Physik der Eberhard-Karls-Universität, Tübingen, September 1997.

*Random domino tilings and the arctic circle theorem*, preprint, 1995. [Ka1]Kast1 P. W. Kasteleyn,

*The statistics of dimers on a lattice, I. The number of dimer arrangements on a quadratic lattice*, Physica

**27**(1961), 1209–1225.

*The planar dimer model with boundary: a survey*, CRM Proceedings and Lecture Notes, to appear.

*Volumes of hyperbolic three-manifolds*, Chapter 7 in lecture notes of W. P. Thurston,

*The Geometry and Topology of Three-manifolds*, Princeton, 1978. [P1]P1 J. Propp,

*Lattice structure for orientations of graphs*, preprint, 1993.

## Additional Information

**Henry Cohn**- Affiliation: Department of Mathematics, Harvard University, Cambridge, Massachusetts 02138
- Address at time of publication: Microsoft Research, One Microsoft Way, Redmond, Washington 98052-6399
- MR Author ID: 606578
- ORCID: 0000-0001-9261-4656
- Email: cohn@math.harvard.edu
**Richard Kenyon**- Affiliation: CNRS UMR 8628, Laboratoire de Topologie, Bâtiment 425, Université Paris-11, 91405 Orsay, France
- MR Author ID: 307971
- Email: kenyon@topo.math.u-psud.fr
**James Propp**- Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706
- MR Author ID: 142280
- Email: propp@math.wisc.edu
- Received by editor(s): January 12, 1999
- Received by editor(s) in revised form: August 11, 2000
- Published electronically: November 3, 2000
- Additional Notes: The first author was supported by an NSF Graduate Research Fellowship. The third author was supported by NSA grant MDA904-92-H-3060 and NSF grant DMS92-06374, and by a grant from the MIT Class of 1922.
- © Copyright 2000 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**14**(2001), 297-346 - MSC (2000): Primary 82B20, 82B23, 82B30
- DOI: https://doi.org/10.1090/S0894-0347-00-00355-6
- MathSciNet review: 1815214

Dedicated: Dedicated to Pieter Willem Kasteleyn (1924–1996)