Domino tiling

Encyclopedia

A

of the region by domino

s, shapes formed by the union of two unit square

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

More details can be found in .

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

, where each such point is connected to four neighbors: if

The sequence of values generated by this formula for squares with

These numbers can be found by writing them as the Pfaffian

of an

.

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

number of tilings drops to the much smaller number D(

, which has only exponential rather than super-exponential growth in

long middle row, there is only one tiling.

**domino tiling**of a region in the Euclidean plane is a tessellationTessellation

A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...

of the region by domino

Domino (mathematics)

In mathematics, a domino is a polyomino of order 2, that is, a polygon in the plane made of two equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to be distinct shapes, there is only one free domino....

s, shapes formed by the union of two unit square

Unit square

In mathematics, a unit square is a square whose sides have length 1. Often, "the" unit square refers specifically to the square in the Cartesian plane with corners at , , , and .-In the real plane:...

s 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 with height 0, then for any node there is a path from to it. On this path define the height of each node (i.e. corners of the squares) to be the height of the previous node plus one if the square on the right of the path from to is black, and minus one else.More details can be found in .

## Thurston's height condition

William ThurstonWilliam Thurston

William Paul Thurston is an American mathematician. He is a pioneer in the field of low-dimensional topology. In 1982, he was awarded the Fields Medal for his contributions to the study of 3-manifolds...

(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 latticeInteger lattice

In mathematics, the n-dimensional integer lattice , denoted Zn, is the lattice in the Euclidean space Rn whose lattice points are n-tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid lattice. Zn is the simplest example of a root 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

The number of ways to cover a -by- rectangle with dominoes, calculated independently by and , is given byThe 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, ... .

These numbers can be found by writing them as the Pfaffian

Pfaffian

In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries. This polynomial is called the Pfaffian of the matrix, The term Pfaffian was introduced by who named them after Johann Friedrich Pfaff...

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 mechanicsStatistical mechanics

Statistical mechanics or statistical thermodynamicsThe terms statistical mechanics and statistical thermodynamics are used interchangeably...

.

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

Aztec diamond

In combinatorial mathematics, an Aztec diamond of order n consists of all squares of a square lattice whose centers satisfy |x| + |y| ≤ n...

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, thenumber of tilings drops to the much smaller number D(

*n*,*n*), a Delannoy numberDelannoy number

In mathematics, a Delannoy number D describes the number of paths from the southwest corner of a rectangular grid to the northeast corner , using only single steps north, northeast, or east....

, which has only exponential rather than super-exponential growth in

*n*. For the "reduced Aztec diamond" of order*n*with only onelong middle row, there is only one tiling.

## See also

- Statistical mechanicsStatistical mechanicsStatistical mechanics or statistical thermodynamicsThe terms statistical mechanics and statistical thermodynamics are used interchangeably...
- Gaussian free fieldGaussian free fieldIn probability theory and statistical mechanics, the Gaussian free field is a Gaussian random field, a central model of random surfaces . A nice survey is ....

, the scaling limit of the height function in the generic situation (e.g., inside the inscribed disk of a large aztec diamond) - Mutilated chessboard problemMutilated chessboard problemThe mutilated chessboard problem is a tiling puzzle introduced by and discussed by Martin Gardner in his Scientific American column "Mathematical Games." The problem is as follows:...

, a puzzle concerning domino tiling of a 62-square subset of the chessboard - TatamiTatamiA is a type of mat used as a flooring material in traditional Japanese-style rooms. Traditionally made of rice straw to form the core , with a covering of woven soft rush straw, tatami are made in standard sizes, with the length exactly twice the width...

, 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