Domino tiling

Domino tiling of a square

A domino tiling of a region in the Euclidean plane is a tessellation of the region by dominos, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.

Height functions

For some classes of tilings on a regular grid in two dimensions, it is possible to define a height function associating an integer to the nodes of the grid. For instance, draw a chessboard, fix a node A₀ with height 0, then for any node there is a path from A₀ to it. On this path define the height of each node A_{n + 1} (i.e. corners of the squares) to be the height of the previous node A_n plus one if the square on the right of the path from A_n to A_{n + 1} is black, and minus one else.

More details can be found in Kenyon & Okounkov (2005).

Thurston's height condition

William Thurston (1990) describes a test for determining whether a simply-connected region, formed as the union of unit squares in the plane, has a domino tiling. He forms an undirected graph that has as its vertices the points (x,y,z) in the three-dimensional integer lattice, where each such point is connected to four neighbors: if x+y is even, then (x,y,z) is connected to (x+1,y,z+1), (x-1,y,z+1), (x,y+1,z-1), and (x,y-1,z-1), while if x+y is odd, then (x,y,z) is connected to (x+1,y,z-1), (x-1,y,z-1), (x,y+1,z+1), and (x,y-1,z+1). The boundary of the region, viewed as a sequence of integer points in the (x,y) plane, lifts uniquely (once a starting height is chosen) to a path in this three-dimensional graph. A necessary condition for this region to be tileable is that this path must close up to form a simple closed curve in three dimensions, however, this condition is not sufficient. Using more careful analysis of the boundary path, Thurston gave a criterion for tileability of a region that was sufficient as well as necessary.

Counting tilings of regions

Domino tiling of an 8×8 square using the minimum number of long-edge-to-long-edge pairs (1 pair in the center).

The number of ways to cover a m-by-n rectangle with mn / 2 dominoes, calculated independently by Temperley & Fisher (1961) and Kasteleyn (1961), is given by

$\prod_{j=1}^m \prod_{k=1}^n \left ( 4\cos^2 \frac{\pi j}{m + 1} + 4\cos^2 \frac{\pi k}{n + 1} \right )^{1/4}.$

The sequence of values generated by this formula for squares with m = n = 0, 2, 4, 6, 8, 10, 12, ... is

1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... (sequence A004003 in OEIS).

These numbers can be found by writing them as the Pfaffian of an mn by mn antisymmetric matrix whose eigenvalues can be found explicitly. This technique may be applied in many mathematics-related subjects, for example, in the classical, 2-dimensional computation of the dimer-dimer correlator function in statistical mechanics.

An Aztec diamond of order 4, with 1024 domino tilings

The number of tilings of a region is very sensitive to boundary conditions, and can change dramatically with apparently insignificant changes in the shape of the region. This is illustrated by the number of tilings of an Aztec diamond of order n, where the number of tilings is 2^(n+1)n/2. If this is replaced by the "augmented Aztec diamond" of order n with 3 long rows in the middle rather than 2, the number of tilings drops to the much smaller number D(n,n), a Delannoy number, which has only exponential rather than super-exponential growth in n. For the "reduced Aztec diamond" of order n with only one long middle row, there is only one tiling.

See also

• Statistical mechanics
• Gaussian free field, the scaling limit of the height function in the generic situation (e.g., inside the inscribed disk of a large aztec diamond)
• Mutilated chessboard problem, a puzzle concerning domino tiling of a 62-square subset of the chessboard
• Tatami, floor mats in the shape of a domino that are used to tile the floors of Japanese rooms, with certain rules about how they may be placed

References

• Bodini, Olivier; Latapy, Matthieu (2003), "Generalized Tilings with Height Functions", Morfismos 7 (1): 47–68, ISSN 1870-6525, http://www-rp.lip6.fr/%7Elatapy/Publis/morfismos03.pdf .
• Kasteleyn, P. W. (1961), "The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice", Physica 27 (12): 1209–1225, doi:10.1016/0031-8914(61)90063-5 .
• Kenyon, Richard (2000), "The planar dimer model with boundary: a survey", Directions in mathematical quasicrystals, CRM Monogr. Ser., 13, Providence, R.I.: American Mathematical Society, pp. 307–328, MR1798998 
• Kenyon, Richard; Okounkov, Andrei (2005), "What is … a dimer?", Notices of the American Mathematical Society 52 (3): 342–343, ISSN 0002-9920, http://www.ams.org/notices/200503/what-is.pdf .
• Propp, James (2005), "Lambda-determinants and domino-tilings", Advances in Applied Mathematics 34 (4): 871–879, arXiv:math.CO/0406301, doi:10.1016/j.aam.2004.06.005 .
• Sellers, James A. (2002), "Domino tilings and products of Fibonacci and Pell numbers", Journal of Integer Sequences 5 (Article 02.1.2), http://www.emis.de/journals/JIS/VOL5/Sellers/sellers4.pdf .
• Thurston, W. P. (1990), "Conway's tiling groups", American Mathematical Monthly (Mathematical Association of America) 97 (8): 757–773, doi:10.2307/2324578, JSTOR 2324578 .
• Wells, David (1997), The Penguin Dictionary of Curious and Interesting Numbers (revised ed.), London: Penguin, p. 182, ISBN 0-14-026149-4 .