Domino tiling

In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge.

Equivalently, it is a perfect 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.

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.

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.

dominoes, calculated independently by Temperley & Fisher (1961) and Kasteleyn (1961), is given by

(sequence A099390 in the OEIS) When both m and n are odd, the formula correctly reduces to zero possible domino tilings.

[1] Another special case happens for squares with m = n = 0, 2, 4, 6, 8, 10, 12, ... is These numbers can be found by writing them as the Pfaffian of an

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.

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.

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.

Tatami are Japanese floor mats in the shape of a domino (1x2 rectangle).

[2] The problem of tiling an irregular room by tatami that meet three to a corner is NP-complete.

[3] There is a one-to-one correspondence between a periodic domino tiling and a ground state configuration of the fully-frustrated Ising model on a two-dimensional periodic lattice.

[4] At the ground state, each plaquette of the spin model must contain exactly one frustrated interaction.