A variational principle for domino tilings

Authors:
Henry Cohn, Richard Kenyon and James Propp

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

Published electronically:
November 3, 2000

MathSciNet review:
1815214

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 (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.

**[BH]**H. W. J. Blöte and H. J. Hilhorst,*Roughening transitions and the zero-temperature triangular Ising antiferromagnet*, J. Phys. A**15**(1982), L631-L637. MR**83k:82046****[BP]**R. Burton and R. Pemantle,*Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances*, Ann. Probab.**21**(1993), 1329-1371. MR**94m:60019****[CEP]**H. Cohn, N. Elkies, and J. Propp,*Local statistics for random domino tilings of the Aztec diamond*, Duke Math. J.**85**(1996), 117-166. MR**97k:52026****[CLP]**H. Cohn, M. Larsen, and J. Propp,*The shape of a typical boxed plane partition*, New York J. Math.**4**(1998), 137-165. MR**99j:60011****[DMB]**N. Destainville, R. Mosseri, and F. Bailly,*Configurational entropy of co-dimension one tilings and directed membranes*, J. of Statistical Physics**87**(1997), 697--754. MR**98i:52029****[EKLP]**N. Elkies, G. Kuperberg, M. Larsen, and J. Propp,*Alternating sign matrices and domino tilings*, J. Algebraic Combin.**1**(1992), 111-132 and 219-234. MR**94f:52035**; MR**94f:52036****[Fe]**H. Federer,*Geometric Measure Theory*, Springer-Verlag, New York, 1969. MR**41:1976****[Fo]**J.-C. Fournier,*Pavage des figures planes sans trous par des dominos: fondement graphique de l'algorithme de Thurston et parallélisation*, Compte Rendus de L'Acad. des Sci., Série I**320**(1995), 107-112. MR**95k:52031****[GT]**D. Gilbarg, N. S. Trudinger,*Elliptic partial differential equations of second order*, Springer, Berlin, 1977. MR**57:13109****[GP]**D. Gupta and J. Propp, work in preparation.**[H]**M. Höffe,*Zufallsparkettierungen und Dimermodelle*, Thesis, Institut für Theoretische Physik der Eberhard-Karls-Universität, Tübingen, September 1997.**[JM]**M. T. Jaekel and J. M. Maillard,*Inversion relations and disorder solutions on Potts models*, J. Phys. A**17**(1984), 2079-2094. MR**86f:82054****[JPS]**W. Jockusch, J. Propp, and P. Shor,*Random domino tilings and the arctic circle theorem*, preprint, 1995.**[Ka1]**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.**[Ka2]**P. W. Kasteleyn,*Dimer statistics and phase transitions*, J. Math. Phys.**4**(1963), 287-293. MR**27:3394****[KR]**C. Kenyon and E. Remila,*Perfect matchings on the triangular lattice*, Discrete Math.**152**(1996), 191-210. MR**97a:05171****[Ke1]**R. Kenyon,*Local statistics of lattice dimers*, Ann. Inst. Henri Poincaré, Probabilités,**33**(1997), 591-618. MR**99b:82039****[Ke2]**R. Kenyon,*The planar dimer model with boundary: a survey*, CRM Proceedings and Lecture Notes, to appear.**[L]**L. S. Levitov,*Equivalence of the dimer resonating-valence-bond problem to the quantum roughening problem*, Phys. Rev. Lett.**64**(1990), 92-94. MR**90k:82078****[MR]**J. M. Maillard and R. Rammal,*-symmetry on the checkerboard Potts model*, J. Phys. A**18**(1984), 833-846. MR**86e:82049****[M]**J. Milnor,*Volumes of hyperbolic three-manifolds*, Chapter 7 in lecture notes of W. P. Thurston,*The Geometry and Topology of Three-manifolds*, Princeton, 1978.**[P1]**J. Propp,*Lattice structure for orientations of graphs*, preprint, 1993.**[P2]**J. Propp,*Boundary-dependent local behavior for 2-D dimer models*, Internat. J. Modern Phys. B**11**(1997), 183-187. MR**98a:82025****[PW]**J. G. Propp and D. B. Wilson,*Exact sampling with coupled Markov chains and applications to statistical mechanics*, Random Structures and Algorithms**9**(1996), 223-252. MR**99k:60176****[R]**W. Rudin,*Real and Complex Analysis*, third edition, McGraw-Hill, New York, 1987. MR**88k:00002****[STCR]**N. Saldanha, C. Tomei, M. Casarin, Jr., and D. Romualdo,*Spaces of domino tilings*, Discrete Comput. Geom.**14**(1995), 207-233. MR**96e:52050****[TF]**H. N. V. Temperley and M. E. Fisher,*Dimer problem in statistical mechanics--an exact result*, Phil. Mag.**6**(1961), 1061-1063. MR**24:B2436****[T]**W. P. Thurston,*Conway's tiling groups*, Amer. Math. Monthly**97**(1990), 757-773. MR**91k:52028**

Retrieve articles in *Journal of the American Mathematical Society*
with MSC (2000):
82B20,
82B23,
82B30

Retrieve articles in all journals with MSC (2000): 82B20, 82B23, 82B30

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

Email:
cohn@math.harvard.edu

**Richard Kenyon**

Affiliation:
CNRS UMR 8628, Laboratoire de Topologie, Bâtiment 425, Université Paris-11, 91405 Orsay, France

Email:
kenyon@topo.math.u-psud.fr

**James Propp**

Affiliation:
Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706

Email:
propp@math.wisc.edu

DOI:
https://doi.org/10.1090/S0894-0347-00-00355-6

Keywords:
Random tiling,
dominos,
variational principle,
matchings,
dimer model

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.

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

Article copyright:
© Copyright 2000
American Mathematical Society